The Fibonacci sequence is named after Leonardo of Pisa - nicknamed Fibonacci - who in his book Liber Abaci reported a series in which each element is always equal to the sum of the two preceding elements, starting with 1 and 1. The first elements of the row are thus:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …
The Fibonacci sequence has some very interesting features, and is, among other things, connected to the golden ratio. It is also used in the theorem of Zeckendorf - named after the Belgian doctor, army officer and mathematician Edouard Zeckendorf. The theorem states that any positive integer can be written in a unique way as the sum of one or more numbers in a Fibonacci sequence that do not follow each other. Such a sum is called the Zeckendorf representation of a number. The Zeckendorf representation of the number 100 is
100 = 3 + 8 + 89
Other ways to write the number 100 as a sum of numbers from the Fibonacci sequence are not sufficient. For example, we can write that
100 = 1 + 2 + 8 + 89
100 = 3 + 8 + 34 + 55
but these sums respectively have 1-2 and 34-55 as successive pairs of numbers in the Fibonacci sequence.
The Zeckendorf representation of a number $$n \in \mathbb{N}_0$$ can be easily found on the basis of a so-called greedy search strategy. Start with the largest number $$m_1$$ from the Fibonacci sequence that is smaller or equal to the integer $$n$$. Then locate the largest number $$m_2$$ from the Fibonacci sequence that is less than or equal to the difference $$n - m_1$$. Keep repeating this process until the difference itself is a number in the Fibonacci sequence.
Write a function zeckendorf to which a number $$n \in \mathbb{N}_0$$ has to be passed as argument. The function must return the Zeckendorf representation of $$n$$ as a string, where the terms appear in ascending order in the sum.
>>> zeckendorf(100)
'3 + 8 + 89'
>>> zeckendorf(848)
'5 + 233 + 610'
>>> zeckendorf(1234)
'1 + 13 + 233 + 987'