In everyday life and science, we use the decimal system in order to represent numbers. Recently I wrote a post that gives a description of the different systems of numeration, used to represent numbers (integers and reals) in an integer base. In the present post I will write about a non-standard numeration system based on Fibonacci numbers, this system is also called Zeckendorf numeration system.
Everybody is familiar with the Fibonacci numbers, i.e.
This sequence is so famous that it is mentioned in Hollywood movies.
We use this sequence in order to represent any integer. First, we recall what is the regular numeration system. For example in the decimal system the number 2017 means:
In general the integer number dn... d1 d0, in base 10 means
where the digits di's are numbers between 0 and 9.
In general for any number p, we can write
where the digits di, are numbers between 0 and p-1. For more details see my previous post on the subject.
The numeration system on Fibonacci numbers is based on the fact any positive integer can be written in a unique way as a sum of nonconsecutive Fibonacci numbers. This is the statement of Zeckendorf's Theorem. We illustrate the idea of the proof with an example: Consider the number 125: its closest Fibonacci number is 89. Then consider the difference 125 - 89 = 36, and apply the same procedure as before to this difference. The closest Fibonacci number to 36 is 34. So we consider their difference 36 - 34 = 2, which is a Fibonacci number so the algorithm stops. Hence we have 125=89+34+2.
Remember that we listed the Fibonacci numbers as follows:
We now can encode all this information in the following manner:
So we can write the number 125 in this encoding or system as "1010000010".
We will show other example: Consider the number 30, its closest Fibonacci number is 21 or f7, the difference is 30 - 21 = 9, which is not Fibonacci, its closest Fibonacci number is 8 or f5 and their difference is 1 or f1, in other words:
So the encoding of the decimal number 125 in the Zeckendorf system is "1010001".
In general any positive integer N can be written as
where the numbers εi are 0 or 1 with the the property of no consecutive "1", i.e.
εiεi+1=0, since that means two consecutive Fibonacci numbers in the sum. This is not possible due to the formation rule of the Fibonacci numbers and the Zeckendorf algorithm described above.
I would like to mention that this numeration system is named after Edourad Zeckendrof (1901-1983) who was a Belgian medical doctor and amateur mathematician.
The following table shows the Zeckendorf representation of the first 16 positive integers.
In a future post I will describe how to represent any real number, using a numeration system based on Fibonacci numbers.
References:
https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem
http://mathworld.wolfram.com/ZeckendorfRepresentation.html
Zeckendorf, E.; "Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas." Bull. Soc. Roy. Sci. Liège 41, 179-182, (1972).
https://en.wikipedia.org/wiki/Edouard_Zeckendorf
Kimberling, Clark; "Edouard Zeckendorf", Fibonacci Quarterly, 36: 416–418 (1998).