Fibonacci coding

In mathematics and computing, Fibonacci coding is a universal code which encodes positive integers into binary code words. It is one example of representations of integers based on Fibonacci numbers. Each code word ends with "11" and contains no other instances of "11" before the end.

The Fibonacci code is closely related to the Zeckendorf representation, a positional numeral system that uses Zeckendorf's theorem and has the property that no number has a representation with consecutive 1s. The Fibonacci code word for a particular integer is exactly the integer's Zeckendorf representation with the order of its digits reversed and an additional "1" appended to the end.

For a number ${\displaystyle N\!}$, if ${\displaystyle d(0),d(1),\ldots ,d(k-1),d(k)\!}$ represent the digits of the code word representing ${\displaystyle N\!}$ then we have:

...
Wikipedia