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
modifierLes 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
modifierCes 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] :
où est le nème entier n'apparaissant pas dans . 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
modifierLa suite G est définie par[3],[4] :
Les premiers termes de la suite sont
Suite H
modifierLa suite H est définie par[3],[5] :
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
modifierLes suites femelles (F) et mâles (M) sont définies par[3],[6] :
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
modifierLa suite Q est définie par[3],[7]
Les premiers termes de cette suite sont
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 2k 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 , autrement dit s'il n'arrive jamais que les indices soient négatifs[10],[15],[17].
Généralisations de la suite Q
modifierFamille de Hofstadter–Huber
modifier20 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
(avec s ≥ 2 et r < s) ; la suite Q initiale est donc la suite Q1,2. Seules trois suites de cette famille semblent définies pour tout ; outre la suite Q = Q1,2, il s'agit des suites V = Q1,4 et W = Q2,4[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
et ceux de la suite W sont
Famille de Pinn
modifierEn 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 Fi,j est définie par[19] :
Les seules suites Fi,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 F0,1 sont :
La suite de Hofstadter–Conway à 10 000 dollars
modifierDouglas Hofstadter et John Horton Conway ont défini la suite ainsi[20] :Les premiers termes de cette suite sont
La suite 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]
Notes et références
modifier- (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).
- Hofstadter 1980, p. 73
- (en) Eric W. Weisstein, « Hofstadter Figure-Figure Sequence », sur MathWorld
- Hofstadter 1980, p. 137
- (en) Eric W. Weisstein, « Hofstadter G-Sequence », sur MathWorld
- (en) Eric W. Weisstein, « Hofstadter H-Sequence », sur MathWorld
- (en) Eric W. Weisstein, « Hofstadter Male-Female Sequences », sur MathWorld
- (en) Eric W. Weisstein, « Hofstadter's Q-Sequence », sur MathWorld
- Pinn 1999, p. 3
- Pinn 2000, p. 1
- Emerson 2006, p. 7
- Pinn 1999, p. 3–4
- Balamohan, Kuznetsov et Tanny 2007, p. 19
- Pinn 1999, Abstract, p. 8
- Pinn 1999, p. 4–5
- Pinn 1999, p. 2
- Pinn 2000, p. 3
- Balamohan, Kuznetsov et Tanny 2007, p. 2
- Balamohan, Kuznetsov et Tanny 2007
- Pinn 2000, p. 16
- (en) Eric W. Weisstein, « Hofstadter-Conway $10,000 Sequence », sur MathWorld
- (en) Michael Tempel, « Easy as 1 1 2 2 3 »
- (en) Colin L. Mallows, « Conway's challenge sequence », The American Mathematical Monthly, vol. 98, no 1, , p. 5–20 (DOI 10.2307/2324028, JSTOR 2324028, MR 1083608)
Sources
modifier- (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, no 7, , 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, no 1, (ISSN 1530-7638, lire en ligne).
- (en) Douglas Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Penguin Books, (ISBN 0-14-005579-7).
- (en) Klaus Pinn, « Order and Chaos in Hofstadter's Q(n) Sequence », Complexity, vol. 4, no 3, , 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, no 1, , p. 55–66 (DOI 10.1080/10586458.2000.10504635, Bibcode 1998cond.mat..8031P, arXiv cond-mat/9808031, S2CID 13519614).