NegaFibonacci Encoding

The NegaFibonacci code uses a variant of Zeckendorf's theorem which states that any integer (relative) can be written as the sum of non-consecutive generalized (positive or negative) Fibonnacci numbers.

$$ n = \sum_{i=1}^{k} \beta_i F_{-i} $$

(note the negative index $ i $) with $ \beta_i $ (equal to 0 or 1)

Example: $ 12 $ is the sum of $ F_{-7} = 13 $ and $ F_{-2} = -1 $ or 1000010 in binary (the two 1 are in position 7 and 2 starting from the right).

This representation similar to Zeckendorf never has 2 consecutive Fibonnacci numbers and therefore the binary value never has 2 consecutive digit 1.

Each 1 of the binary word corresponds to a NegaFibonacci number (number of the Fibonacci sequence generalized to negative numbers). So, to calculate the original decimal number, add all the NegaFibonacci numbers corresponding to the 1 of the binary word.

Example: 10100 corresponds to $ 1 \times F_{-5} + 0 \times F_{-4} + 0 \times F_{-3} + 1 \times F_{-2} + 0 \times F_{-1} = F_{-5} + F_{-3} = 5 + 2 = 7 $

NegaFibonacci encoding is already a variant of Fibonacci encoding. It has the advantage of being generalizable to relative numbers (positive or negative integers).