Thought Process

Using Zeckendorf's Theorem we know that we can find the Zeckendorf representation of a number by using a greedy algorithm, this inherently tells us that there will be some sort of recursive algorithm which repeats because of it's greedy property.

The way I approached the problem is by looking at the wikipedia picture, which I cannot post here due to copyright issues, and noticing there are "blocks" which repeat after each Fibonacci number

1. Let block1 = {red block, yellow block}

   • This represents the number 1 = f_1, 2 = f_2

2. block2 = {brown block, red block}

   • This represents the number 3 = f_3, 4 = f_1 + f_3

3. Now for example the next block would be the light green one which represents the 4th fibonacci number, 5.

   • Then we add the previous fibonacci number, 3, and block1 and we get blockn = block1 + 3

     1. You can think of the addition like so:

        1. 5 + 0 = 5

        2. 5 + 1 = 6

        3. 5 + 2 = 7

     2. We have now found representation of all numbers between 5 and 8

   • As illustrated above there are 3 numbers between 5 and 8, the next fibonacci number, and within those 3 we are going to repeat block1

   • set block1 += block2

   • set block2 = blockn

   • repeat till we get to the largest possible fibonacci number

Using this we have a code which will find the correct sum of z(n) if n is a Fibonacci number!

How do we deal with non-fibonacci numbers? Split the number into the largest fibonacci number possible and the remainder, and recursively apply the algorithm to the remainder and the original part.