Aller au contenu

Théorème de Zeckendorf

Ce théorème stipule que tout nombre entier positif peut s’écrire de façon unique comme somme d’entiers, tous différents, figurant dans la suite de Fibonacci, où ces entiers :

  • sont tous différents ;
  • ne sont pas consécutifs dans la suite ;
  • sont pris à partir du rang 2 au moins.

Tout le monde connaît la suite de Fibonacci, qui commence par \(u_0=0\), \(u_1=1\) et où chaque entier est la somme des 2 précédents \(u_{n+2}=u_{n+1}+u_n\) ce qui donne : 0 1 1 2 3 5 8 13 21, etc.

Sans la restriction de la non-consécutivité, la somme n’est pas unique. En effet, \(17=13+3+1\) mais on a aussi \(17=8+5+3+1\).

 

Il est commode de représenter sous forme « binaire » la représentation de Zeckendorf. Pour 17, on aurait

  • \(17=(1\times13)+(0\times8)+(0\times5)+(1\times3)+(0\times2)+(1\times1)\) qui s’écrit \(17=100101\) ;
  • \(17=(1\times8)+(1\times5)+(1\times3)+(1\times1)\) qui s’écrit\(17=1111\).

 

Nous allons afficher à l’aide de TeX, pour chaque entier de 1 à 50 (ou tout entier arbitraire), une décomposition de Zeckendorf. Afin que l’algorithme reste simple, peu importe si les entiers de la suite de Fibonacci sont consécutifs.

 

Le processus commence par générer la suite de Fibonacci (à partir du rang 2) dont la somme est au moins égale au nombre dont on veut la décomposition sous la forme 21,13,8,5,3,2,1, pour 50 par exemple (on a bien \(21+13+8+5+3+2+1>50\)). L’algorithme n’est pas efficace puisqu’il génère cette suite pour chaque nombre allant de 1 à 50, ce qui est évidemment un énorme gaspillage de temps qu’il serait facile d’économiser.

L’algorithme est naïf ; il initialise deux variables :

  • somme cible est le nombre à décomposer ;
  • somme fibo est nulle.

Le cœur de l’algorithme, contenu dans la macro \zeckendorfaux parcourt chaque nombre i dans la liste de Fibonnacci de gauche à droite : i est retenu dans la décomposition si somme fibo<somme cible. Dans ce cas, on ajoute i à somme fibo et on le retire à somme cible puis on recommence avec le prochain nombre dans la liste.

 

On obtient la sortie pdf dans un lap de temps imperceptible.

Laisser un commentaire