Integers as (unique) sums of Fibonacci numbers

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.

Eddie Zeckendorf’s result gets a whole Wikipedia page, as does Eddie himself, who was a Belgian doctor, army officer (retiring as Colonel) and mathematician.

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 $5k^2-4, 5k^2+4$ 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.

Thanks Ira!

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 $k^{th}$ Fibonacci number $\textrm{F}_k$ is just the floor of (the largest integer below) $\frac{\phi^k}{\sqrt{5}}+1/2$ , where $\phi= \frac{1+\sqrt{5}}{2}$ .

Denoting the floor of a real number $x$ by $\lfloor x\rfloor$ this gives us a very simple, and quick way to calculate the largest Fibonacci number $\textrm{F}_k \leq n$ :