suite d'Hofstadter

Écrivez d'abord 1, 1. Pour trouver un nouveau terme, les deux valeurs précédentes ne disent pas quoi additionner, mais où retourner dans la liste. Au rang 8, les valeurs 5 et 4 font remonter aux rangs 3 et 4 ; on y lit 2 et 3, dont la somme vaut 5.

La suite d'Hofstadter se construit ainsi en utilisant ses propres valeurs comme adresses. Ce jeu de renvois explique pourquoi sa règle est courte, tandis que son évolution demeure difficile à prévoir.

La suite d'Hofstadter est une suite d'entiers indexée par les entiers strictement positifs. La valeur au rang n est notée u(n). Les deux valeurs initiales sont u(1) = 1 et u(2) = 1.

Pour tout rang n supérieur à 2, on calcule deux rangs en retranchant de n chacune des deux valeurs qui précèdent. On additionne ensuite les termes situés à ces rangs : Les expressions n − u(n−1) et n − u(n−2) sont donc des indices, pas les valeurs à additionner. La source garantit que cette règle définit bien la suite.

Cette récurrence est imbriquée : les valeurs antérieures déterminent les emplacements d'autres valeurs antérieures. Les premiers termes montrent des paliers et même des baisses ponctuelles, par exemple de u(15) = 10 à u(16) = 9. La suite est calculable terme après terme, mais son comportement asymptotique reste partiellement ouvert.

La construction repose sur quatre éléments. Les deux termes initiaux, u(1) et u(2), amorcent la suite. Le rang courant n indique le terme à produire. Les deux termes précédents, u(n−1) et u(n−2), servent à fabriquer les indices de retour. Enfin, les valeurs lues à ces deux indices sont additionnées.

Les dépendances sont doubles : changer une valeur antérieure modifie d'abord un indice, puis potentiellement la valeur trouvée à cet indice. Les deux retours peuvent aussi aboutir au même rang ; pour n = 3, ils pointent tous deux vers le rang 2. Ces données et la règle suffisent à calculer les termes successifs ; leur mise en page ou leur tracé ne fait pas partie de la définition.

Calculons le terme de rang 8. Les termes déjà connus sont, dans l'ordre des rangs 1 à 7 : 1, 1, 2, 3, 3, 4 et 5. En particulier, u(6) = 4 et u(7) = 5.

1. Le premier indice de retour vaut 8 − u(7) = 8 − 5 = 3.
2. Le second indice de retour vaut 8 − u(6) = 8 − 4 = 4.
3. Aux rangs 3 et 4, on lit respectivement u(3) = 2 et u(4) = 3.
4. La règle donne donc u(8) = u(3) + u(4) = 2 + 3 = 5.

Le résultat est l'entier 5. Pour contrôler le calcul, il suffit de vérifier séparément les deux soustractions, puis de relire les valeurs aux rangs 3 et 4 dans la liste initiale. Le schéma associé rend visibles ces deux retours.

Pour prolonger la liste à la main, on conserve les rangs au-dessus des valeurs. À chaque nouvelle ligne, on calcule d'abord les deux indices de retour, puis on lit et additionne les termes correspondants. Cette organisation évite de confondre un indice avec une valeur.

Pour produire beaucoup de termes, un programme peut stocker toutes les valeurs déjà calculées. Une récurrence plus directe convient mieux si chaque terme ne dépend que d'un nombre fixe de voisins immédiats ; ici, les rangs consultés changent avec la suite elle-même.

Pour explorer son comportement, on peut comparer la liste des termes, leurs paliers et leurs baisses ponctuelles. Ces observations guident les questions, mais elles ne suffisent pas à conclure sur le comportement asymptotique, qui reste partiellement ouvert.

Avec la suite de Fibonacci. Dans la suite de Fibonacci, deux termes immédiatement précédents sont additionnés. Dans la suite d'Hofstadter, ces deux termes servent d'abord à choisir des rangs plus anciens. Au rang 8, le calcul utilise ainsi les rangs 3 et 4, non les valeurs des rangs 7 et 6 comme termes à sommer.

Avec une définition circulaire. Le terme u(n) n'est pas utilisé pour se calculer lui-même. Sa règle consulte des valeurs déjà obtenues ; la source précise que la suite est bien définie. Le fait que ses valeurs servent d'indices crée une récurrence imbriquée, pas une équation sans point de départ.

Les deux retours peuvent coïncider. Pour n = 3, les deux indices valent 2. Il faut alors compter deux fois le terme u(2), ce qui donne u(3) = 1 + 1 = 2 ; supprimer le doublon fausserait la suite.

La suite n'est pas croissante terme à terme. Le passage de u(15) = 10 à u(16) = 9 fournit un contre-exemple visible. Il faut examiner les valeurs calculées plutôt que prolonger les premiers paliers par intuition.

Une longue liste ne prouve pas une loi asymptotique. Même si de nombreux termes sont calculables, leur comportement pour des rangs arbitrairement grands ne se déduit pas d'un échantillon fini. La source indique précisément que ce comportement reste partiellement ouvert.

La suite de Fibonacci offre un contrepoint utile : sa récurrence additionne directement les deux termes précédents, sans utiliser leurs valeurs comme indices.

L'article Équations linéaires et suites récurrentes ne font qu'un ! prolonge l'étude des suites récurrentes dans un cadre linéaire, à comparer avec l'imbrication propre à la suite d'Hofstadter.