The 1024 Function Problem- Edited
Number Theory
Level
2
F(1) = 1
F(2n) = 2F(n)
F(2n+1) = 4F(n)
How many positive integer solutions are there for n where F(n) = 1024?
The answer is 89.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Step 1: Write out the first 16 terms in the sequence
F(1) = 1
F(2) = 2
F(3) = 4
F(4) = 4
F(5) = 8
F(6) = 8
F(7) = 16
F(8) = 8
F(9) = 16
F(10) = 16
F(11) = 32
F(12) = 16
F(13) = 32
F(14) = 32
F(15) = 64
F(16) = 16
You need to be able to spot that n >= F(n) by looking at the functions in the question; this allows us to proceed to the next step with confidence.
Step 2: Count the number of solutions there are for each F(n) value
There is only one solution for F(n) = 1; n=1
There is only one solution for F(n) = 2; n=2
There are only two solutions for F(n) = 4; n=3, n=4 etc.
F(n) = 1 -> 1 solution
F(n) = 2 -> 1 solution
F(n) = 4 -> 2 solutions
F(n) = 8 -> 3 solutions
F(n) = 16 -> 5 solutions
Note: cannot go further since we only listed the first 16 terms.
In the small sequence above, it is clear that the pattern in the number of solutions is identical to the Fibonacci sequence.
Step 3: Continue with the Fibonacci sequence until you get to 1024
F(n) = 1 -> 1 solution
F(n) = 2 -> 1 solution
F(n) = 4 -> 2 solutions
F(n) = 8 -> 3 solutions
F(n) = 16 -> 5 solutions
F(n) = 32 -> 8 solutions
F(n) = 64 -> 13 solutions
F(n) = 128 -> 21 solutions
F(n) = 256 -> 34 solutions
F(n) = 512 -> 55 solutions
F(n) = 1024 -> 89 solutions