# Suite de Hofstadter

En mathématiques, une suite de Hofstadter est une suite d'entiers faisant partie d'une famille définie par des relations de récurrence non linéaires, et plus précisément dans lesquelles chaque terme est défini à partir des termes d'indices correspondants aux termes précédents.

## Suites apparaissant dans Gödel, Escher, Bach

Les premières suites de Hofstadter furent décrites par Douglas Richard Hofstadter dans son livre Gödel, Escher, Bach : Les Brins d'une Guirlande Éternelle en 1979. Par ordre d'apparition dans ce livre, ce sont :

### Suites Figure-Figure

Ces suites, apparaissant dans le chapitre III (Figure et fond) et faisant allusion à un ambigramme de Scott Kim, sont deux suites d'entiers complémentaires définies par$^,$ :
    ${\begin{aligned}R(1)&=1~;\ S(1)=2\\R(n)&=R(n-1)+S(n-1),\quad n>1.\end{aligned}}$
où $S(n)$ est le n-ième entier n'apparaissant pas dans $R$. Les premiers termes de ces suites sont :
    R : 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260, ... (suite A005228 de l'OEIS) ;
    S : 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ... (suite A030124 de l'OEIS).

### Suite G

La suite G est définie par$^,$ :
    ${\begin{aligned}G(0)&=0\\G(n)&=n-G(G(n-1)),\quad n>0.\end{aligned}}$
Les premiers termes de la suite sont
    0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, ... (suite A005206 de l'OEIS).

### Suite H

La suite H est définie par$^,$ :
    ${\begin{aligned}H(0)&=0\\H(n)&=n-H(H(H(n-1))),\quad n>0.\end{aligned}}$
Les premiers termes de la suite sont
    0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, ... (suite A005374 de l'OEIS).

### Suites mâles et femelles

Les suites femelles (F) et mâles (M) sont définies par$^,$ :
    ${\begin{aligned}F(0)&=1~;\ M(0)=0\\F(n)&=n-M(F(n-1)),\quad n>0\\M(n)&=n-F(M(n-1)),\quad n>0.\end{aligned}}$
Les premiers termes de ces suites sont
    F: 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, ... (suite A005378 de l'OEIS) ;
    M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, ... (suite A005379 de l'OEIS).

### Suite Q

La suite Q est définie par$^,$
    ${\begin{aligned}Q(1)&=Q(2)=1,\\Q(n)&=Q(n-Q(n-1))+Q(n-Q(n-2)),\quad n>2.\end{aligned}}$
Les premiers termes de cette suite sont
    1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, ... (suite A005185 de l'OEIS).
Il s'agit d'une « méta-suite de Fibonacci », chaque terme étant la somme, non des deux termes précédents, mais celle des deux termes dont les indices sont fonction des deux termes précédents.
Bien que les termes de la suite Q semblent chaotiques$^,$$^,$$^,$, on peut les regrouper par blocs de générations successives, comme pour beaucoup d'autres suites du même type$^,$ ; dans le cas de la suite Q, la k-ème génération a 2$^k$ termes$^,$.
Ces résultats sont pour la plupart des observations empiriques ou des conjectures$^,$$^,$ ; on ignore même en fait si la suite est définie pour tout $n$, autrement dit s'il n'arrive jamais que les indices $n-Q(n-1)$ soient négatifs$^,$$^,$.

## Généralisations de la suite Q
### Famille de Hofstadter–Huber

20 ans après que Hofstadter eut décrit la suite Q, lui et Greg Huber la généralisèrent à une famille obtenue en remplaçant dans la suite Q les indices (n − 1) et (n − 2) par (n − r) et (n − s), respectivement ; on a donc
    $Q_{r,s}(n)={\begin{cases}1,\quad 1\leq n\leq s,\\Q_{r,s}(n-Q_{r,s}(n-r))+Q_{r,s}(n-Q_{r,s}(n-s)),\quad n>s,\end{cases}}$
(avec s ≥ 2 et r < s) ; la suite Q initiale est donc la suite Q$_{1,2}$. Seules trois suites de cette famille semblent définies pour tout $n$ ; outre la suite Q = Q$_{1,2}$, il s'agit des suites V = Q$_{1,4}$ et W = Q$_2$,$_4$$^,$ ; mais la suite V (au comportement moins chaotique que les autres) est la seule démontrée être toujours définie.
Les premiers termes de la suite V sont
    1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, ... (suite A063882 de l'OEIS)
et ceux de la suite W sont
    1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, ... (suite A087777 de l'OEIS).

### Famille de Pinn

En 1998, Klaus Pinn, chercheur à l'université de Münster en communication étroite avec Hofstadter, suggéra d'autres généralisations de la suite Q, les suites F.
La suite F$_{i,j}$ est définie par :
    $F_{i,j}(n)={\begin{cases}1,\quad n=1,2,\\F_{i,j}(n-i-F_{i,j}(n-1))+F_{i,j}(n-j-F_{i,j}(n-2)),\quad n>2.\end{cases}}$
Les seules suites F$_{i,j}$ qui semblent définies pour tout indice sont celles pour lesquelles (i,j) = (0,0), (0,1), (1,0), ou (1,1) (la première étant la suite Q originelle).
Les premiers termes de la suite F$_{0,1}$ sont :
    1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, 11, ... (suite A046699 de l'OEIS).

## La suite de Hofstadter–Conway à 10 000 dollars

Douglas Hofstadter et John Horton Conway ont défini la suite $a$ ainsi :${\begin{aligned}a(1)&=a(2)=1,\\a(n)&=a{\biga(n-1){\big )}+a{\bign-a(n-1){\big )},\quad n>2.\end{aligned}}$Les premiers termes de cette suite sont
    1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, ... (suite A004001 de l'OEIS).
La suite $a(n)/n$ converge vers 1/2 ; la suite a acquis son nom parce que Conway a offert un prix de 10 000 $ à qui pourrait déterminer sa vitesse de convergence. Ce prix (ramené à 1000 $), fut gagné par Collin Mallows, qui démontra que$^,$ $\left|{\frac {a(n)}{n}}-{\frac {1}{2}}\right|=O\left({\frac {1}{\sqrt {\log n}}}\right).$