Problèmes autour des représentations de Zeckendorf

Représentation minimale de Zeckendorf

Définition des nombres de Fibonacci

On rappelle que la suite de Fibonacci est définie par

\[F_n = \begin{cases} n & \text{si } n < 2\\ F_{n-1} + F_{n-2} & \text{si } n \geqslant 2 \end{cases}\]

On a le tableau de valeurs :

\[\begin{array}{c|ccccccccccccccc} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\\ \hline F_n & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377 & 610\\ \end{array}\]

Le cadre

On considère la suite tronquée de Fibonacci. Il n'y a plus le zéro, ni le un en doublon.

On parlera désormais de nombres de Fibonacci, au lieu de la suite.

\[1, 2, 3, 5, 8, 13, 21 ,34, 55, 89, 144, 233, 377, 610,...\]

On s'intéresse à des sommes avec des nombres de Fibonacci distincts.

Exemple

On peut écrire \(100\) comme somme de nombres de Fibonacci de plusieurs façons, sans compter l'ordre :

\(100 = 3 + 8 + 89\)
\(100 = 1 + 2 + 8 + 89\)
\(100 = 1 + 2 + 3 + 5 + 89\)
\(100 = 3 + 8 + 34 + 55\)
\(100 = 1 + 2 + 8 + 34 + 55\)
\(100 = 1 + 2 + 3 + 5 + 34 + 55\)
\(100 = 3 + 8 + 13 + 21 + 55\)

Mais, il n'y a qu'une seule somme qui fait intervenir des nombres de Fibonacci en effectif minimal. (On note que ces nombres ne sont pas consécutifs dans leur liste.)

\[100 = 3 + 8 + 89\]

On admettra, ou vous démontrerez, que ceci se généralise pour tout entier !

Exemples de 0 à 34 ; représentation minimale

\(0\) est une somme vide.
\(1 = 1\) ; une somme à un seul élément.
\(2 = 2\) ; une somme à un seul élément.
\(3 = 3\) ; une somme à un seul élément.
\(4 = 3 + 1\) ; une somme à deux éléments.
\(5 = 5\)
\(6 = 5 + 1\)
\(7 = 5 + 2\)
\(8 = 8\)
\(9 = 8 + 1\)
\(10 = 8 + 2\)
\(11 = 8 + 3\)
\(12 = 8 + 3 + 1\)
\(13 = 13\)
...
\(33 = 21 + 8 + 3 + 1\)
\(34 = 34\)
...

Théorème de Zeckendorf

Tout entier naturel s'écrit de manière unique comme somme de nombres de Fibonacci, distincts et non consécutifs dans leur liste, sans compter l'ordre des termes. Il s'agit de la représentation minimale.

Démontré par Édouard Zeckendorf (1901 - 1983) ; médecin belge, officier de l'armée, et mathématicien.

Exemples de représentations minimales

\(100 = 3 + 8 + 89\)
\(20 = 2 + 5 + 13\)
\(1 = 1\)
\(0\) est égal à une somme vide

On peut associer à chaque représentation une liste de bits.

🐍 Script Python

# Indices                       0  1  2  3  4  5  6  7  8  9 10 11
# Nombres de Fibonacci          1  2  3  5  8 13 21 34 55 89 (144 ...
assert zeckendorf_repr(100) == [0, 0, 1, 0, 1, 0, 0, 0, 0, 1]
assert zeckendorf_repr(20)  == [0, 1, 0, 1, 0, 1]
assert zeckendorf_repr(1)   == [1]
assert zeckendorf_repr(0)   == []

Aucune liste de bits dans la représentation minimale ne contient deux 1 consécutifs.

Représentation maximale

Représentations maximale de Zeckendorf

Rappel : Pour un entier donné, il existe plusieurs représentations.

Exemple

\(100 = 3 + 8 + 89\)
\(100 = 1 + 2 + 8 + 89\)
\(100 = 1 + 2 + 3 + 5 + 89\)
\(100 = 3 + 8 + 34 + 55\)
\(100 = 1 + 2 + 8 + 34 + 55\)
\(100 = 1 + 2 + 3 + 5 + 34 + 55\)
\(100 = 3 + 8 + 13 + 21 + 55\)

On peut démontrer que pour un entier \(n\), il existe une unique représentation de Zeckendorf, comme somme de nombres de Fibonacci distincts, avec un nombre maximal de termes. On dit alors que c'est la représentation maximale de Zeckendorf. Il n'y en a pas d'autre avec plus de termes.

Exemple: La représentation maximale de Zeckendorf de \(100\) est : \(1 + 2 + 3 + 5 + 13 + 21 + 55\)

🐍 Script Python

# Indices               0  1  2  3  4  5  6  7  8  9 10 11
# Nombres de Fibonacci  1  2  3  5  8 13 21 34 55 89 (144 ...
assert zeckendorf_eval([1, 1, 1, 1, 0, 1, 1, 0, 1]) == 1 + 2 + 3 + 5 + 13 + 21 + 55 == 100

Dans ce cas,

La liste de bits ne contient pas deux 0 consécutifs.

Le graphe des représentations

Pour un entier fixé, les différentes représentations appartiennent à un graphe connexe, où les arêtes correspondent à une transformation \(F_{k}=F_{k-1}+F_{k-2}\).

C'est une excellente idée pour certaines démonstrations.

---
title: Graphe des représentations de Zeckendorf de 100
---
graph TB
    A["3 + 8 + 89"]
    B["1 + 2 + 8 + 89"]
    C["1 + 2 + 3 + 5 + 89"]
    D["3 + 8 + 34 + 55"]
    E["1 + 2 + 8 + 34 + 55"]
    F["1 + 2 + 3 + 5 + 34 + 55"]
    G["3 + 8 + 13 + 21 + 55"]
    I["1 + 2 + 8 + 13 + 21 + 55"]
    H["1 + 2 + 3 + 5 + 13 + 21 + 55"]
    A <--> B & D
    B <--> C & E
    C & E <--> F
    D <--> G & E
    E & G <--> I
    F & I <--> H

Pour démontrer que le graphe est connexe, on peut construire un algorithme pour rejoindre la représentation minimale (ou la maximale) ; c'est un des exercices proposés.

Questions mathématiques facultatives (avec calculs informatiques)

Exercice

Démontrer le théorème de Zeckendorf sur la représentation minimale. Puis celui sur la représentation maximale.

Exercice

On pourra noter le bloc '11111111...1' de taille k, comme k * '1'
On pourra noter le bloc '01010101010101...1' de taille 2*k, comme k * '01'
On pourra noter le bloc '101010101010101...1' de taille 2*k + 1, comme '1' + k * '01' ou k * '10' + '1'

On se demande alors

Ajouter le nombre \(1\) à la somme représentée par k * '10' + '1'
Ajouter le nombre \(1\) à la somme représentée par k * '1'

Quelles sont les formules mathématiques associées à ces transformations ?

Exercice

Quelle est la représentation minimale qui correspond à un bloc de uns ?

Réponse

Cette méthode sera très utile pour l'exercice Minimum

Exercice

Quels sont les nombres qui n'ont qu'une seule représentation ?

Réponse

Voir la partie graphe, la question sur les graphes qui n'ont qu'un seul sommet.

Exercice

Démontrer que pour \(n > 0\),

le nombre de zéros au début (ceux de poids faible) dans la représentation minimale de Zeckendorf est pair, si et seulement si, la représentation maximale comporte \(F_2=1\)
le nombre de uns au début (ceux de poids faible) dans la représentation maximale de Zeckendorf est pair, si et seulement si, la représentation minimale comporte \(F_2=1\).

Exercice

Déterminer les représentations minimales de \(F_n^2\) et \(F_n × F_{n+1}\) pour quelques petites valeurs de \(n\).
Trouver une règle et démontrer ce fait.

Réponse

On constate que pour

\(n > 1\) et pair, \(F_n^2\) a pour motif : '1' + (n // 2 - 1) * '0001'
\(n > 1\) et impair, \(F_n^2\) a pour motif : '101' + (n // 2 - 1) * '0001'
\(n > 1\) et pair, \(F_n^2×F_{n+1}\) a pour motif : '01' + (n // 2 - 1) * '0001'
\(n > 1\) et impair, \(F_n×F_{n+1}\) a pour motif : '1001' + (n // 2 - 1) * '0001'

Exercice

Démontrer que pour \(m>0\) et \(n\geqslant 0\), \(F_{mn}\) est divisible par \(F_m\).
Déterminer les représentations de \(F_{mn}/F_m\) pour quelques petites valeurs de \(m\) et \(n\).
Trouver une règle et démontrer ce fait.

Exercice

Trouver une formule additive (sans soustraction) pour une somme de nombres de Fibonacci consécutifs.