théorème de Zeckendorf

Prenons les nombres de Fibonacci 1, 2, 3, 5, 8, 13… et cherchons à former 100. Une règle interdit de choisir deux voisins de cette liste. En prenant chaque fois le plus grand nombre qui ne dépasse pas ce qu’il reste, on obtient 89, puis 8, puis 3.

Ces trois nombres totalisent 100 et aucun n’est voisin d’un autre dans la suite. Le théorème de Zeckendorf garantit que tout entier positif possède une telle décomposition et qu’il n’en existe qu’une respectant ces règles.

Le théorème de Zeckendorf porte sur les entiers naturels strictement positifs. Pour éviter l’ambiguïté créée par les deux termes égaux à 1 dans certaines indexations de Fibonacci, on utilise ici la suite 1, 2, 3, 5, 8… Les nombres de cette liste sont notés F₂, F₃, F₄… Pour tout indice k au moins égal à 4, ils vérifient la relation suivante : $F_k=F_{k-1}+F_{k-2}F\_k=F\_\{k-1\}+F\_\{k-2\}$.

Pour chaque entier positif, il existe une unique somme de termes F_k qui sont tous distincts et dont deux indices ne se suivent jamais. Cette somme est sa représentation de Zeckendorf. « Non consécutifs » concerne donc les positions dans la suite de Fibonacci, et pas seulement des valeurs entières qui ne se suivent pas.

L’existence vient d’un algorithme glouton : à chaque étape, on retire du reste le plus grand terme de Fibonacci qui ne le dépasse pas. L’unicité s’appuie sur le fait qu’une somme admissible dont le plus grand terme est F_k reste strictement inférieure à F_k+1.

Si un nombre est un entier naturel strictement positif, alors il s’écrit d’une et une seule manière comme somme de nombres de Fibonacci distincts, non nuls et non consécutifs. Avec la convention F₂ = 1 et F₃ = 2, les indices de deux termes retenus ne diffèrent jamais de 1.

Le nombre à décomposer doit être un entier naturel strictement positif. Les termes autorisés appartiennent à une même suite de Fibonacci, ils sont non nuls, distincts et séparés par au moins un indice. L’algorithme reçoit l’entier et la liste ordonnée des termes ; il s’arrête lorsque le reste atteint 0 et fournit alors la représentation unique.

Si l’on conserve les deux copies de 1 d’une suite écrite 0, 1, 1, 2…, l’entier 1 semble avoir deux écritures selon la copie choisie. L’unicité est alors masquée par l’indexation. Il faut fixer la convention 1, 2, 3, 5… ou, de façon équivalente, n’autoriser qu’un seul terme égal à 1.

Décomposons l’entier 100. Les données sont le nombre de départ 100 et la suite 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…

1. Le plus grand terme inférieur ou égal à 100 est 89 ; le reste vaut 100 − 89 = 11.
2. Le plus grand terme inférieur ou égal à 11 est 8 ; le reste vaut 11 − 8 = 3.
3. Le plus grand terme inférieur ou égal à 3 est 3 ; le reste vaut 3 − 3 = 0. L’algorithme s’arrête.

La représentation obtenue est $100=89+8+3100=89+8+3$. Le contrôle est double : la somme vaut bien 100, et les indices 11, 6 et 4 des termes choisis ne sont jamais consécutifs. La figure rend visibles ces trois termes et leur total.

Pour obtenir la représentation canonique d’un entier positif, on applique directement l’algorithme glouton. À chaque reste, le choix du plus grand Fibonacci disponible détermine le terme suivant ; il n’est pas nécessaire d’essayer toutes les sommes possibles.

Pour contrôler une décomposition proposée, on additionne ses termes, puis on vérifie leurs positions dans la suite. Si la somme est correcte mais que deux indices sont consécutifs, l’écriture n’est pas encore une représentation de Zeckendorf ; on la remplace par la sortie de l’algorithme glouton.

Si le but est seulement d’écrire un entier dans une base usuelle, une écriture binaire ou décimale convient mieux. La représentation de Zeckendorf devient pertinente lorsque les termes de Fibonacci et l’interdiction de voisins font partie du problème.

Une somme de nombres de Fibonacci. Une égalité comme 10 = 5 + 3 + 2 utilise bien des nombres de Fibonacci, mais 3 et 2 sont consécutifs dans la suite. Ce n’est donc pas une représentation de Zeckendorf ; 10 = 8 + 2 respecte la condition.

Une écriture dans une base à puissances fixes. En base 10 ou en base 2, chaque position porte une puissance de 10 ou de 2. La représentation de Zeckendorf emploie des nombres de Fibonacci, dont chaque terme est la somme des deux précédents, avec l’interdiction de sélectionner deux positions voisines.

Zéro et entiers négatifs. L’énoncé donné concerne les entiers strictement positifs, donc commence à 1. Pour 0, la somme vide est une convention naturelle, mais elle n’est pas couverte par cet énoncé. Pour un entier négatif, il faut choisir une extension distincte au lieu d’appliquer directement le théorème.

Les deux termes égaux à 1. Le symptôme est une apparente double représentation de 1. Il faut annoncer l’indexation et travailler avec F₂ = 1, F₃ = 2, ou exclure explicitement l’autre copie de 1.

Une somme correcte mais non admissible. L’égalité numérique ne suffit pas : 10 = 5 + 3 + 2 comporte des termes voisins. On reprend l’algorithme glouton jusqu’au reste 0, ce qui donne 10 = 8 + 2.

Un choix glouton mal appliqué. Choisir un terme seulement parce qu’il est grand peut produire un reste négatif. À chaque étape, le terme retenu doit être le plus grand nombre de Fibonacci inférieur ou égal au reste courant.

La suite de Fibonacci précise la récurrence et l’indexation des termes employés dans toute représentation de Zeckendorf.

L’algorithme replace la procédure gloutonne dans la notion générale de suite finie d’opérations conduisant à un résultat.