flat assembler
Message board for the users of flat assembler.

 Index > Heap > A little math problem
Author
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:
, where 1 <= N <= 10000.

Any idea?
17 Dec 2011, 08:42
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17270
revolution
F(11) = 11 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?
17 Dec 2011, 08:56
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17270
revolution
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!
17 Dec 2011, 09:00
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.
17 Dec 2011, 12:39
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.
17 Dec 2011, 18:27
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.
18 Dec 2011, 03:28
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.
18 Dec 2011, 05:33
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}

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    ```
18 Dec 2011, 06:34
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17270
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}

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
18 Dec 2011, 06:48
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17270
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]

What is my prize?
18 Dec 2011, 08:23
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.
18 Dec 2011, 14:41
TmX

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

What is my prize?

Well you miss, just a bit
18 Dec 2011, 14:42
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17270
revolution
TmX wrote:
So F(11) is 11, not 22.
Okay. So in that case the answer is: 1111981904675169
18 Dec 2011, 15:19
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17270
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?
18 Dec 2011, 16:01
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17270
revolution
Playing with the mathematical equation generator, can I say the sum is this?

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

18 Dec 2011, 16:16
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
What technique did you use? BFS?
20 Dec 2011, 16:07
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17270
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?
21 Dec 2011, 02:19
TmX

Joined: 02 Mar 2006
Posts: 821
Location: Jakarta, Indonesia
TmX
Hmm no luck yet. I got an segmentation fault
Time to improve the algorithm...
21 Dec 2011, 13:48
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum