# Project Euler 297 - Zeckendorf Representation # 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