flat assembler
Message board for the users of flat assembler.

Index > Heap > A little math problem

Author
Thread Post new topic Reply to topic
TmX



Joined: 02 Mar 2006
Posts: 821
Location: Jakarta, Indonesia
TmX
Given an integer N, the function F(N) returns the smallest integer divisible by N, and this integer only uses the digits 0, 1, or 2 (of course this is decimal representation).

Examples:
F(4) = 12
F(5) = 10
F(11) = 1001
F(42) = 210

Now the problem is to calculate:
Image, where 1 <= N <= 10000.

Any idea? Very Happy
Post 17 Dec 2011, 08:42
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
F(11) = 11 Question Why not?

And perhaps, F(x) = 0 since everything divides zero. So I submit my code:
Code:
sum(N=1,10000)_F(N)/N = 0    
Did I win?
Post 17 Dec 2011, 08:56
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
Additional:
TmX wrote:
returns the smallest integer divisible by N
Seems I missed that point. So F(x) = -∞, since ∞ is the most composite number then it divides everything. So my new submission (please ignore my previous submission) is:
Code:
sum(N=1,10000)_F(N)/N = -infinity    
Do I win a prize now?

Why doesn't ∞ render in the code window!
Post 17 Dec 2011, 09:00
View user's profile Send private message Visit poster's website Reply with quote
smiddy



Joined: 31 Oct 2004
Posts: 559
smiddy
The pseudo code would be, the function, then compare the output to those base characters from the answer to the required set of digits, and once you have a winner, display it.

Another way to do it would be to have a table of all those numbers from 1 to 10,000 and compare the divisibility of N without a remainder starting with the lowest number to the highest to get your answer. (This is likely faster than the first algorithm, there are only so many numbers with 0,1,2 in them for 1 to 10,000; there are many more numbers that do not contain 0,1, and/or 2) Test these out and let us know how it worked.
Post 17 Dec 2011, 12:39
View user's profile Send private message Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
The math problem presented here by TmX isn't so trivial as one may think at first sight. Firstly, the formulation of the problem missed very important information that F(N) has to be the smallest integer divisible by N and greater than N. Secondly, F(N) has to be a multiply of N that is noted using only three digits 0, 1 and 2 (in decimal numbering system). The last condition makes us wondering if for every given N such a number exists at all.

BTW, shouldn't be F(11) = 22 ?


@revolution

-∞ and ∞ aren't integer numbers. These objects are symbols of actual infinities but in Z (set of all integer numbers) we haven't actual infinities. We may realize only potential infinity, i.e. we can always construct a number greater than a given one (or less than any given negative number).

The set of integers consists of the numbers that can be constructed using finite sequence of operations of addition or subtraction. The actual infinities can't be constructed this way.
Post 17 Dec 2011, 18:27
View user's profile Send private message Visit poster's website Reply with quote
smiddy



Joined: 31 Oct 2004
Posts: 559
smiddy
If N can only = the lowest of these 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102,...,10,000 numbers.

What is confusing is the way it is written: sum of F(N)/N from 1 to N, which appears separate from the function F(N). 11 = N, the smallest integer divided by 11 is 11, which satisfies the 0, 1, or 2 digit criteria, therefor the sum of 1 to 11 for 11/11 = 11. N is constant in the equation portion of the summation, and in the sum it changes. At least that was how I read it...

I could be missing something though, I haven't toyed with these in a while.
Post 18 Dec 2011, 03:28
View user's profile Send private message Reply with quote
Xorpd!



Joined: 21 Dec 2006
Posts: 161
Xorpd!
MHajduk wrote:
Secondly, F(N) has to be a multiply of N that is noted using only three digits 0, 1 and 2 (in decimal numbering system). The last condition makes us wondering if for every given N such a number exists at all.


This is guaranteed by Euler's theorem.
Post 18 Dec 2011, 05:33
View user's profile Send private message Visit poster's website Reply with quote
bdo1964



Joined: 18 Sep 2011
Posts: 7
bdo1964
Code:
the answer appears to be...

there are no multiples of 99 that consist of
only {0,1,2} 
-> f(n)    does not exist for 99
-> the sum does not exist for 99 
-> the 10,000 is just fluff

possible combinations for 99*10^0
99*1 = 99
99*2 =198
99*3 =297
99*4 =396
99*5 =495
99*6 =594
99*7 =693
99*8 =792
99*9 =891
possible combinations for 99*10^1
99*10 = 990
99*20 =1980
99*30 =2970
99*40 =3960
99*50 =4950
99*60 =5940
99*70 =6930
99*80 =7920
99*90 =8910

note only 
99*8  = 792
99*9  = 891
and
99*80 =7920
99*90 =8910

have least [nonzero] significant digits within: {0,1,2}
else they are already disqualified

also note that the 2nd most significant digit
is always a 9

this leaves 
7+9=16 [6 carry 1]
or 
8+9=17 [7 carry 1]

7+1=8 and 8+1=9
as the most significant digit

this pattern persists since it a "shl" base 10 

therefore...

either you disqualify yourself with the least [nonzero] significant digit
or...  you disqualify yourself with the only possibilities for the most 
significant digit    
Post 18 Dec 2011, 06:34
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
bdo1964 wrote:
Code:
the answer appears to be...

there are no multiples of 99 that consist of
only {0,1,2} 
-> f(n)    does not exist for 99
-> the sum does not exist for 99 
-> the 10,000 is just fluff

possible combinations for 99*10^0
99*1 = 99
99*2 =198
99*3 =297
99*4 =396
99*5 =495
99*6 =594
99*7 =693
99*8 =792
99*9 =891
possible combinations for 99*10^1
99*10 = 990
99*20 =1980
99*30 =2970
99*40 =3960
99*50 =4950
99*60 =5940
99*70 =6930
99*80 =7920
99*90 =8910

note only 
99*8  = 792
99*9  = 891
and
99*80 =7920
99*90 =8910

have least [nonzero] significant digits within: {0,1,2}
else they are already disqualified

also note that the 2nd most significant digit
is always a 9

this leaves 
7+9=16 [6 carry 1]
or 
8+9=17 [7 carry 1]

7+1=8 and 8+1=9
as the most significant digit

this pattern persists since it a "shl" base 10 

therefore...

either you disqualify yourself with the least [nonzero] significant digit
or...  you disqualify yourself with the only possibilities for the most 
significant digit    
Except that 11335578 * 99 = 1122222222
Post 18 Dec 2011, 06:48
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
Assuming this:
MHajduk wrote:
F(N) has to be the smallest integer divisible by N and greater than N. Secondly, F(N) has to be a multiply of N that is noted using only three digits 0, 1 and 2 (in decimal numbering system).
And assuming this:

Total = sum for(N=1,10000) [F(N)/N]

Then the answer is: 1111981904675695

What is my prize?
Post 18 Dec 2011, 08:23
View user's profile Send private message Visit poster's website Reply with quote
TmX



Joined: 02 Mar 2006
Posts: 821
Location: Jakarta, Indonesia
TmX
MHajduk wrote:
The math problem presented here by TmX isn't so trivial as one may think at first sight. Firstly, the formulation of the problem missed very important information that F(N) has to be the smallest integer divisible by N and greater than N. Secondly, F(N) has to be a multiply of N that is noted using only three digits 0, 1 and 2 (in decimal numbering system). The last condition makes us wondering if for every given N such a number exists at all.

BTW, shouldn't be F(11) = 22 ?


Sorry if I was unclear.
First, indeed F(N) has to be smalelst integer divisible by N, but it doesn't have to be greater that N.
Second, the digits allowed are only 0, 1, or 2. That means the number doesn't have to have 0, 1, and 2 simultaneously.

So F(11) is 11, not 22.
Post 18 Dec 2011, 14:41
View user's profile Send private message Reply with quote
TmX



Joined: 02 Mar 2006
Posts: 821
Location: Jakarta, Indonesia
TmX
revolution wrote:

Then the answer is: 1111981904675695

What is my prize?


Well you miss, just a bit Very Happy
Post 18 Dec 2011, 14:42
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
TmX wrote:
So F(11) is 11, not 22.
Okay. So in that case the answer is: 1111981904675169
Post 18 Dec 2011, 15:19
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
So, let's reverse the problem.

Assuming: Total = sum for(N=1,x) [F(N)/N]

Given the Total as this: 2514778617178067

What is x?
Post 18 Dec 2011, 16:01
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
Playing with the mathematical equation generator, can I say the sum is this?

Image


Description:
Filesize: 1.09 KB
Viewed: 4290 Time(s)

sumfN.png


Post 18 Dec 2011, 16:16
View user's profile Send private message Visit poster's website Reply with quote
TmX



Joined: 02 Mar 2006
Posts: 821
Location: Jakarta, Indonesia
TmX
revolution wrote:
TmX wrote:
So F(11) is 11, not 22.
Okay. So in that case the answer is: 1111981904675169


Yes, you are absolutely right: 1111981904675169 Very Happy
What technique did you use? BFS?
Post 20 Dec 2011, 16:07
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17270
Location: In your JS exploiting you and your system
revolution
TmX wrote:
What technique did you use? BFS?
Basic Fasm Source-code. I just used incremental search with a few short-cuts thrown in to improve the search time. Takes just a few seconds to get the answer.

Do you have a solution for my follow-up problem?
Post 21 Dec 2011, 02:19
View user's profile Send private message Visit poster's website Reply with quote
TmX



Joined: 02 Mar 2006
Posts: 821
Location: Jakarta, Indonesia
TmX
Hmm no luck yet. I got an segmentation fault Sad
Time to improve the algorithm...
Post 21 Dec 2011, 13:48
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.