Did you know that 100000000000 = 86267571272 + 12586269025 + 1134903170+ 9227465 + 1346269+ 514229 + 121393 + 46368 +610 + 144 + 55 and that all the numbers in the sum on the right are Fibonacci numbers?
Not only that:
- no two of these Fibonacci numbers is consecutive in the set of all Fibonacci numbers;
- this is the only way to write 100000000000 as a sum of non-consecutive Fibonacci numbers;
- the software and code used to calculate this did the calculation in under one-tenth of a second.
The bloke who first twigged to this was Eddie (Edouard) Zeckendorf in 1939, but not published until 33 years later in the Fibonacci Quarterly: Zeckendorf, E. (1972). A generalized Fibonacci numeration. Fibonacci Quart, 10, 365-372.
Although Eddie (Edouard) Zeckendorf came up with the decomposition, now known by his name, in 1939 he was beaten to the punch in publication by a Dutch mathematician Cornelis Gerrit Lekkerkerker by some 20 years.
Although Eddie snoozed and let Gerrit beat him to the punch, this decomposition is now generally known as the Zeckendorf decomposition.
I feel, however, to be fair to the good Dr. Lekkerkerker we should , at the very least, refer to this as the Zeckendorf-Lekkerkerker decomposition, or ZL-decomposition for short (just because “Zeckendorf-Lekkerkerker” is quite a Belgian-Dutch mouthful).
The ZL-decomposition of a positive integer n can be implemented as a greedy algorithm in which we search for the largest Fibonacci number below n, subtract this from n, and then do it over until we stop at a Fibonacci number.
For example, if n=70, we know, from a list of Fibonacci numbers, that 55 is the largest Fibonacci number below 70, and then 70-55 = 15, and the largest Fibonacci number below 15 is 13, and the largest Fibonacci number below 15-13 is 2, so we end up with 70 = 55 + 13 +2 as a unique sum of non-consecutive Fibonacci numbers.
But this approach relies on a pre-existing list, and if n is big we will have to generate a big list of Fibonacci numbers on the fly.
If we had a way of recognizing Fibonacci numbers we could start with n and work our way down through n-1, n-2, n-3, … until we hit a Fibonacci number: potentially slow, but at least we wouldn’t have to generate a table on the fly.
There is indeed a simple way of recognizing if a given positive integer k is a Fibonacci number.
A positive integer k is a Fibonacci number if, and only if, one or both of is a perfect square.
This was proven, and published in 1972, by Ira Gessel, then a 21 year old mathematics student at Harvard.
So this gives a nifty, computationally cheap, way of recognizing exactly which positive integers are Fibonacci numbers without having to generate and scan a list of Fibonacci numbers.
But scanning the integers n-1, n-2, n-3, … below a given n to see which is first a Fibonacci number is a slow business: if n = 100000000000 we have to take 13732428728 steps before we hit the Fibonacci number 86267571272.
There is, it turns out, a much faster way.
This faster way relies on the fact that the Fibonacci number is just the floor of (the largest integer below) , where .
Denoting the floor of a real number by this gives us a very simple, and quick way to calculate the largest Fibonacci number :
- first calculate ;
- then compute .
So our greedy algorithm for the ZL-decomposition now goes:
- Input n;
- Compute and as above;
- Replace n with ;
- Repeat until we get a Fibonacci number for ;
- Output with
and this is fast!