Codage de NegaFibonacci

Le code de NegaFibonacci utilise une variante du théorème de Zeckendorf qui indique que tout nombre entier (relatif) peut s'écrire comme la somme de nombres de Fibonnacci généralisés (positifs ou négatifs) non consécutifs.

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

(noter l'indice $ i $ négatif) avec $ \beta_i $ (valant 0 ou 1)

Le codage NegaFibonnacci est la concaténation des coefficients binaires $ \beta_i $ pour en faire un nombre binaire.

Exemple : $ 12 $ est la somme de $ F_{-7} = 13 $ et $ F_{-2} = -1 $ soit 1000010 en binaire (les deux 1 sont en position 7 et 2 en partant de la droite).

Cette représentation similaire à Zeckendorf ne possède jamais 2 nombres de Fibonnacci consécutifs et donc la valeur binaire n'a jamais 2 fois le chiffre 1 consécutivement.

Chaque 1 du mot binaire correspond à un nombre de NegaFibonacci (nombre de la suite de Fibonacci généralisée aux nombres négatifs). Ainsi, pour calculer le nombre décimal original, ajouter tous les nombres de NegaFibonacci correspondant aux 1 du mot binaire.

Exemple : 10100 correspond à $ 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 $

Le codage NegaFibonacci est déjà une variante du codage de Fibonacci. Il a pour avantage d'être généralisable aux nombres relatifs (entiers positifs ou négatifs).