Project Euler 297 - Zeckendorf Representation

Official link:

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.

Interactive Code

Input an integer (yourinput)

Code will output ∑ z(n) for 0 < n < yourinput