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[1],[2] :

${\displaystyle {\begin{aligned}R(1)&=1~;\ S(1)=2\\R(n)&=R(n-1)+S(n-1),\quad n>1.\end{aligned}}}$

où ${\displaystyle S(n)}$ est le n-ième entier n'apparaissant pas dans ${\displaystyle 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[3],[4] :

${\displaystyle {\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[3],[5] :

${\displaystyle {\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[3],[6] :

${\displaystyle {\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[3],[7]

${\displaystyle {\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[3],[8],[9],[10], on peut les regrouper par blocs de générations successives, comme pour beaucoup d'autres suites du même type[11],[12] ; dans le cas de la suite Q, la k-ème génération a 2^k termes[13],[14].

Ces résultats sont pour la plupart des observations empiriques ou des conjectures[15],[16],[17] ; on ignore même en fait si la suite est définie pour tout ${\displaystyle n}$, autrement dit s'il n'arrive jamais que les indices ${\displaystyle n-Q(n-1)}$ soient négatifs[10],[15],[17].

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[17] ; on a donc

${\displaystyle 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 ${\displaystyle n}$ ; outre la suite Q = Q_1,2, il s'agit des suites V = Q_1,4 et W = Q₂,₄[17],[18] ; mais la suite V (au comportement moins chaotique que les autres) est la seule démontrée être toujours définie[17].

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[19].

La suite F_i,j est définie par[19] :

${\displaystyle 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)[19].

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 ${\displaystyle a}$ ainsi[20] :$${\displaystyle {\begin{aligned}a(1)&=a(2)=1,\\a(n)&=a{\big (}a(n-1){\big )}+a{\big (}n-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 ${\displaystyle 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[21],[22] $${\displaystyle \left|{\frac {a(n)}{n}}-{\frac {1}{2}}\right|=O\left({\frac {1}{\sqrt {\log n}}}\right).}$$

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hofstadter sequence » (voir la liste des auteurs).

1. Hofstadter 1980, p. 73
2. (en) Eric W. Weisstein, « Hofstadter Figure-Figure Sequence », sur MathWorld
3. Hofstadter 1980, p. 137
4. (en) Eric W. Weisstein, « Hofstadter G-Sequence », sur MathWorld
5. (en) Eric W. Weisstein, « Hofstadter H-Sequence », sur MathWorld
6. (en) Eric W. Weisstein, « Hofstadter Male-Female Sequences », sur MathWorld
7. (en) Eric W. Weisstein, « Hofstadter's Q-Sequence », sur MathWorld
8. Pinn 1999, p. 3
9. Pinn 2000, p. 1
10. Emerson 2006, p. 7
11. Pinn 1999, p. 3–4
12. Balamohan, Kuznetsov et Tanny 2007, p. 19
13. Pinn 1999, Abstract, p. 8
14. Pinn 1999, p. 4–5
15. Pinn 1999, p. 2
16. Pinn 2000, p. 3
17. Balamohan, Kuznetsov et Tanny 2007, p. 2
18. Balamohan, Kuznetsov et Tanny 2007
19. Pinn 2000, p. 16
20. (en) Eric W. Weisstein, « Hofstadter-Conway $10,000 Sequence », sur MathWorld
21. (en) Michael Tempel, « Easy as 1 1 2 2 3 »
22. (en) Colin L. Mallows, « Conway's challenge sequence », The American Mathematical Monthly, vol. 98, n^o 1,‎ 1991, p. 5–20 (DOI 10.2307/2324028, JSTOR 2324028, MR 1083608)

Sources

• (en) B. Balamohan, A. Kuznetsov et Stephan M. Tanny, « On the Behaviour of a Variant of Hofstadter's Q-Sequence », University of Waterloo, Waterloo, Ontario (Canada), vol. 10, n^o 7,‎ 27 juin 2007, p. 71 (ISSN 1530-7638, Bibcode 2007JIntS..10...71B, lire en ligne).
• (en) Nathaniel D. Emerson, « A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions », University of Waterloo, Waterloo, Ontario (Canada), vol. 9, n^o 1,‎ 17 mars 2006 (ISSN 1530-7638, lire en ligne).
• (en) Douglas Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Penguin Books, 1980 (ISBN 0-14-005579-7).
• (en) Klaus Pinn, « Order and Chaos in Hofstadter's Q(n) Sequence », Complexity, vol. 4, n^o 3,‎ 1999, p. 41–46 (DOI 10.1002/(SICI)1099-0526(199901/02)4:3<41::AID-CPLX8>3.0.CO;2-3, Bibcode 1999Cmplx...4c..41P, arXiv chao-dyn/9803012v2).
• (en) Klaus Pinn, « A Chaotic Cousin of Conway's Recursive Sequence », Experimental Mathematics, vol. 9, n^o 1,‎ 2000, p. 55–66 (DOI 10.1080/10586458.2000.10504635, Bibcode 1998cond.mat..8031P, arXiv cond-mat/9808031, S2CID 13519614).