Zeckendorf’s theorem says that every positive integer can be represented as the sum of non-consecutive Fibonacci integers and that such a representation is unique.

For example:
100 = 89 + 8 + 3
10,000 = 6765 + 2584 + 610 +34 + 5 + 2

Notice though that there are many ways to represent an integer as the sum of Fibonacci numbers but only 1 way to represent them using non-consecutive Fibonacci numbers.

Personally, I’ve always found theorems like this to be pretty neat, but I’ve also always felt that tediously reading through proofs to be less interesting than just discovering the end result. Through induction you can prove existence and uniqueness, if you’re so inclined to read through the proof, check out: Proof of Zeckendorf’s Theorem

It turns out that this type of representation is very easy to generate programmatically. Let’s say we want to break the integer N into fibonacci numbers, since we know every number can be broken into fibonacci numbers, if we substract some fibonacci number from N, the remaining difference can also be broken down into more fibonacci numbers. Through repeated subtraction of fibonacci numbers, we can build this representation. Though, to ensure that the fibonacci numbers that are being subtracted are part of the Zeckendorf representation (non-consecutive fibonacci numbers) we make sure to test the numbers from largest fib posible to smallest. This would be considered a ‘Greedy’ solution.

Here is a code implementation which reads in a number to break down and prints out the Zeckendorf fibonacci representation. We generate 35 fibonacci numbers, which is enough to break all numbers < Fib(35), which is around 9 million. Every time we find a fibonacci number which is less than or equal to our number, we substract it and decrement out current_fib counter an additional time so we do not choose consecutive fibonacci numbers.

We don’t ever make sure that out curr_fib counter goes below zero because we are ensured that every number has a Zeckendorf representation through the ‘existence’ property.

#include <iostream>
using namespace std;

int main()
{
  // Let's compute 35 fibonacci numbers, this is pretty large. 9,227,465
  int fib[35];
  fib[0] = 1;
  fib[1] = 1;
  for(int i=2;i<35;++i)
  {
    fib[i] = fib[i-1] + fib[i-2];
  }

  int number;
  cin >> number; // Read in a number to break down

  int curr_fib = 34; // Index of the largest fibonacci number in our fib array
  while(number > 0)
  {
    if(number >= fib[curr_fib])
    {
      number -= fib[curr_fib];
      cout << fib[curr_fib] << endl; // Print out
      --curr_fib; // Do not choose consecutive fibs, let's skip the next one
    }
    --curr_fib;
  }
}