Zeckendorf's theorem

The Zeckendorf's theorem states that every positive integer can be represented uniquely as a sum of one or more distinct non-neighboring or non-consecutive Fibonacci numbers. The sequence of Fibonacci numbers which add up to N is called the Zeckendorf representation of N.

Fibonacci numbers form a Fibonacci sequence where each number is the sum of the two preceding numbers. The first two terms of the sequence are 0 and 1.
First 20 Fibonacci numbers are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181.

Theorem: Let N be a positive integer. Then there's a unique increasing sequence $(c_{i})_{i=0}^{k}$ where $(c_{i} \geq 2)$
such that $\ c_{i+1} > c_{i} +1 \ for \ \ i \geq 0$.

$$N = \sum_{i=0}^{k} F_{c_{i}}$$
Here F represents a Fibonacci number. Such a sequence of Fibonacci numbers adding up to N is called the Zeckendorf representation for N.

Examples

Zeckendorf representation of 10 is 2 + 8. The representation 2 + 3 + 5 wouldn't be a Zeckendorf representation as the Fibonacci numbers in sequence are consecutive Fibonacci numbers.

Zeckendorf representation of 100 is 89+8+3.

Zeckendorf representation of 71 is 55+13+3.

1. The Zeckendorf representation of N can be found by subtracting the greatest Fibonacci number not greater than N, say the Fibonacci number is N1.
2. If this does not result in zero, the greatest Fibonacci number not greater than (N-N1), say N2 is to be subtracted from (N-N1).
3. If the subtraction results in 0, the Zeckendorf representation is found, else repeat till the subtraction of the next greatest Fibonacci number from the remainder results in 0. Then the Zeckendorf representation is found.
4. The Zeckendorf representation shouldn't include two consecutive Fibonacci numbers.

• The Zeckendorf representation of any positive integer can be found using a greedy algorithm, the greatest possible Fibonacci number is chosen at each stage of the algorithm.

• The Zeckendorf representation cannot consist of two neighboring or consecutive Fibonacci numbers. Consider F(1) the first Fibonacci number, F(2) the second Fibonacci number and F(N) the Nth Fibonacci number and so on.

F(1) = 0, F(2) = 1, F(3) = 1, F(4) = 2, F(5) = 3, F(6) = 5.
We can see that F(5) + F(3) = 3 + 1 = 4
4 < 5                  (next Fibonacci number is 5)
F(6) = 5
F(5) + F(3) < F(6)

• If we assume that the sums of non-consecutive Fibonacci numbers up to F(j−1) are all less than F(j).
• Similarly the sum up to F(j) will not contain F(j-1) and will be a sum of F(j) and a non-consecutive sum of Fibonacci numbers up to F(j-2) which is smaller than F(j-1) as seen above.
• If not, F(j-1) would be the greatest Fibonacci number smaller than the given number rather than F(j) which is the actual greatest Fibonacci number smaller than the given number.
• Hence the Zeckendorf representation of a positive number is represented using non-consecutive Fibonacci numbers.

Program

#include <iostream>

using namespace std;


int fitFibonacci(int N)
{   
    //first three terms of the Fibonacci sequence
    int p = 0, q = 1, r = 1;
    
    if(N == 0 || N == 1)
    return N;
    
    //finding the greatest Fibonacci number that is smaller than the number N.
    while(r <= N){
        p = q;
        q = r;
        r = p + q;
    }
    
    return q;
    
}

int main()
{
    int N = 111;
    cout << "Fibonacci representation of " << N << ": ";
    
    int rem = N ,num = 0;
    
    //greedy algorithm runs till the remainder is zero.
    while(rem > 0)
    {
       //finding the greatest Fibonacci number smaller than the given number. 
       num = fitFibonacci(rem);
       cout << num << " ";
       rem = rem - num;
    }
}

Output
Fibonacci representation of 111: 89 21 1

Time Complexity: O(N * LogN)

Negafibonacci numbers
The Fibonacci numbers for negative index are called the negafibonacci numbers. The negafibonacci sequence numbers satsify the following equation:

$$F_{-n} = (-1)^{n+1}F_{n}$$

Any integer can be uniquely written as the sum of negafibonacci numbers consisting of no consecutive negafibonacci numbers.

Examples
−11 = F(−4) + F(−6) = (−3) + (−8)
11 = F(-7) + F(-4) + F(1) = 13 + (-3) + 1
25 = F(-9) + F(-6) + F(-2) = 34 + (-8) + (-1)

Fibonacci coding

• The Zeckendorf representation of a number has a property that the binary value of the number doesn't contain two consecutive 1s since the representation never has 2 consecutive Fibonnacci numbers.
• Fibonacci coding uses Zeckendorf representation and encodes positive integers into binary code words or binary strings.
• Each binary string ends with "11" and doesn't contain any other "11" before it.
• The Fibonacci code word for a positive integer is the integer's Zeckendorf representation with the order of its digits reversed and an additional "1" appended to the end.

Example
Here FC(N) represents the Fibonacci code of the number N.
FC(65) = 0100100011
0100100011 is the Fibonacci encoding of 65.

Decoding:
From left and with starting index as 2 the 1's in the Fibonacci coding are in positions 3, 6 and 19. Hence the sum of F(3), F(6) and F(10) will be 65.

1×F(10) + 0×F(9) + 0×F(8)+ 0×F(7) + 1×F(6) + 0×F(5) + 0×F(4) + 1×F(3) + 0×F(2) = F(10) + F(6) + F(3)

F(10) + F(6) + F(3) = 55 + 8 + 2 = 65

With this article at OpenGenus, you must have the complete idea of Zeckendorf's theorem.