Fibonacci number system

Posted on by John

Every positive integer can be written as the sum of distinct Fibonacci numbers. For example, 10 = 8 + 2, the sum of the fifth Fibonacci number and the second.

This decomposition is unique if you impose the extra requirement that consecutive Fibonacci numbers are not allowed. [1] It’s easy to see that the rule against consecutive Fibonacci numbers is necessary for uniqueness. It’s not as easy to see that the rule is sufficient.

Every Fibonacci number is itself the sum of two consecutive Fibonacci numbers—that’s how they’re defined—so clearly there are at least two ways to write a Fibonacci number as the sum of Fibonacci numbers, either just itself or its two predecessors. In the example above, 8 = 5 + 3 and so you could write 10 as 5 + 3 + 2.

The nth Fibonacci number is approximately φn/√5 where φ = 1.618… is the golden ratio. So you could think of a Fibonacci sum representation for x as roughly a base φ representation for √5x.

You can find the Fibonacci representation of a number x using a greedy algorithm: Subtract the largest Fibonacci number from x that you can, then subtract the largest Fibonacci number you can from the remainder, etc.

Programming exercise: How would you implement a function that finds the largest Fibonacci number less than or equal to its input? Once you have this it’s easy to write a program to find Fibonacci representations.

* * *

[1] This is known as Zeckendorf’s theorem, published by E. Zeckendorf in 1972. However, C. G. Lekkerkerker had published the same result 20 years earlier.

8 thoughts on “Fibonacci number system”

  1. I can’t find Lekkerkerker’s 1951 paper, nor Zeckendorf 1972 but my understanding is that Zeckendorf discovered his theorem in 1939. David Daykin’s 1960 JLMS paper on the subject says “Zeckendorf’s proof is given by C. G. Lekkerkerka (sic)”. Lekkerkerker’s paper, I understand, went on to present a theorem on the average number of summands in a Zeckendorf representation.

  3. I could use the approximation for the n-th Fibonacci number you gave for the exercise and calculate:

    x = log(input * sqrt(5)) / log(phi)

    Now take the precise formula by Binet/Moivre:

    fib(n) = (phi^n – (1 – phi)^n) / sqrt(5)

    If fib(ceil(x)) equals the input, than that’s the solution, otherwise it’s fib(floor(x)).

  4. Pseudonym

    By the way, this numbering system makes a great alternative to Elias codes for compressing integers. Base-Fibonacci numbers greater than zero have a “canonical” form where there is a 1 in the leftmost place, and there are no two consecutive “1” digits. The first few are 1, 10, 100, 101, 1000, 1001, 1010, 10000.

    If you reverse the digits and add a trailing 1, you have a canonical prefix-free encoding of the positive integers: 11, 011, 0011, 1011, 00011, 10011, 01011 etc.

    One advantage of this system is that unlike the other logarithmic codes, you can detect the code boundaries without having to decode them; the code boundaries are exactly the double-1’s.

  5. Nico

    The previous binary observation could be used to find the largest Fibonacci term. Observing the binary representation of the input, go from LSB to MSB, and remove appropriate 1 bits whenever there are repeated sequences of 1 bits. It’s important to turn ones into zero bits such that you keep the largest number afterwards.

Comments are closed.