Suite de Conway
La suite de Conway est une suite mathématique inventée en 1986 par le mathématicien anglo-saxon John Horton Conway, initialement sous le nom de « suite audioactive »<ref>Modèle:Article.</ref>. Elle est également connue sous le nom anglais de Modèle:Lang (« regarde et dis »).
Dans cette suite, un terme se détermine en annonçant les chiffres formant le terme précédent.
Définition
Le premier terme de la suite de Conway est posé comme égal à 1. Chaque terme de la suite se construit en annonçant le terme précédent, c'est-à-dire en indiquant combien de fois chacun de ses chiffres se répète.
Concrètement :
- <math>X_0 = 1</math>
Ce terme comporte simplement un « 1 ». Par conséquent, le terme suivant est :
- <math>X_1 = 11</math>
Celui-ci est composé de deux « 1 » :
- <math>X_2 = 21</math>
En poursuivant le procédé :
- <math>X_3 = 1211</math>
- <math>X_4 = 111221</math>
- <math>X_5 = 312211</math>
- <math>X_6 = 13112221</math>
Et ainsi de suite.
Il est possible de généraliser le procédé en prenant un terme initial différent de 1. Dans le reste de l'article, on supposera que le terme initial vaut 1.
Les 20 premiers termes
| Terme | |
|---|---|
| 1 | 1 |
| 2 | 11 |
| 3 | 21 |
| 4 | 12 11 |
| 5 | 11 12 21 |
| 6 | 31 22 11 |
| 7 | 13 11 22 21 |
| 8 | 11 13 21 32 11 |
| 9 | 31 13 12 11 13 12 21 |
| 10 | 13 21 13 11 12 31 13 11 22 11 |
| 11 | 11 13 12 21 13 31 12 13 21 13 21 22 21 |
| 12 | 31 13 11 22 21 23 21 12 11 13 12 21 13 12 11 32 11 |
| 13 | 13 21 13 21 32 11 12 13 12 21 12 31 13 11 22 21 13 11 12 21 13 12 21 |
| 14 | 11 13 12 21 13 12 11 13 12 31 12 11 13 11 22 21 12 13 21 13 21 32 21 13 31 22 21 13 11 22 11 |
| 15 | 31 13 11 22 21 13 11 12 31 13 11 12 13 21 12 31 13 21 32 21 12 11 13 12 21 13 12 11 13 22 21 23 11 32 21 13 21 22 21 |
| 16 | 13 21 13 21 32 21 13 31 12 13 21 13 31 12 11 13 12 21 12 13 21 13 12 11 13 22 21 12 31 13 11 22 21 13 11 12 31 13 32 11 12 13 21 13 22 21 13 12 11 32 11 |
| 17 | 11 13 12 21 13 12 11 13 22 21 23 21 12 11 13 12 21 23 21 12 31 13 11 22 21 12 11 13 12 21 13 11 12 31 13 32 21 12 13 21 13 21 32 21 13 31 12 13 21 23 12 31 12 11 13 12 21 13 32 21 13 11 12 21 13 12 21 |
| 18 | 31 13 11 22 21 13 11 12 31 13 32 11 12 13 12 21 12 31 13 11 22 11 12 13 12 21 12 13 21 13 21 32 21 12 31 13 11 22 21 13 31 12 13 21 23 22 21 12 11 13 12 21 13 12 11 13 22 21 23 21 12 11 13 12 11 12 13 11 12 13 21 12 31 13 11 22 21 23 22 21 13 31 22 21 13 11 22 11 |
| 19 | 13 21 13 21 32 21 13 31 12 13 21 23 12 31 12 11 13 11 22 21 12 13 21 13 21 22 31 12 11 13 11 22 21 12 11 13 12 21 13 12 11 13 22 21 12 13 21 13 21 32 21 23 21 12 11 13 12 11 12 13 32 21 12 31 13 11 22 21 13 11 12 31 13 32 11 12 13 12 21 12 31 13 11 12 31 12 11 13 31 12 11 13 12 21 12 13 21 13 21 32 11 12 13 32 21 23 11 32 21 13 21 22 21 |
| 20 | 11 13 12 21 13 12 11 13 22 21 23 21 12 11 13 12 11 12 13 11 12 13 21 12 31 13 21 32 21 12 11 13 12 21 13 12 11 22 13 21 12 31 13 21 32 21 12 31 13 11 22 21 13 11 12 31 13 32 21 12 11 13 12 21 13 12 11 13 22 11 12 13 12 21 12 31 13 11 12 31 12 11 23 22 21 12 13 21 13 21 32 21 13 31 12 13 21 23 12 31 12 11 13 11 22 21 12 13 21 13 31 12 13 21 12 31 23 21 12 31 13 11 22 21 12 11 13 12 21 13 12 11 13 12 31 12 11 23 22 11 12 13 21 13 22 21 13 12 11 32 11 |
Propriétés
La suite de Conway a de multiples propriétés. Certaines d'entre elles sont indiquées ci-dessous, avec, pour les plus simples, les démonstrations correspondantes.
- Aucun terme de la suite ne comporte un chiffre supérieur à 3.
- Tous les termes de la suite possèdent un nombre pair de chiffres, sauf le terme initial.
- À partir du quatrième terme, les termes de rang pair se terminent par 211 et les termes de rang impair par 221.
- À partir du huitième terme, les termes commencent cycliquement par "1113", "3113" et "1321".
- La suite de Conway est strictement croissante, ainsi que celle des L(n) où L(n) est le nombre de chiffres constituant le n-ième terme de la suite de Conway.
- En moyenne, les termes de la suite possèdent 50 % de chiffres 1, 31 % de 2 et 19 % de 3.Modèle:Référence nécessaire
- Le nombre <math>L_n</math> de chiffres du n-ième terme de la suite est équivalent à Cλn, où λ ≈ Modèle:Nombre<ref>Pour plus de décimales, voir la Modèle:OEIS - jusqu'à la 20000e.</ref> est un entier algébrique de degré 71 nommé constante de Conway<ref>Modèle:MathWorld.</ref>,<ref name=":0">Modèle:Lien web</ref>, et C est une autre constante. En particulier :
- <math>\lim_{n \to +\infty}\frac{L_{n+1}}{L_{n}} = \lambda</math>
- Cette propriété reste vraie dans le cas général<ref>Modèle:Ouvrage.</ref> où le premier terme de la suite est choisi différent de 1 (et de 22, puisque dans ce cas la suite est constante), avec une constante C qui dépend de ce choix, mais avec toujours la même constante λ.
La constante de Conway est l'unique solution réelle positive de l'équation polynomiale suivante<ref>Suite Modèle:OEIS2C de l'OEIS.</ref> :
- <math>\begin{align}
&\,\,\,\,\,\,\,x^{71} && &&-x^{69} &&-2x^{68}&&-x^{67} &&+2x^{66} &&+2x^{65}&&+x^{64}&&-x^{63}\\ &-x^{62} &&-x^{61} &&-x^{60} &&-x^{59} &&+2x^{58}&&+5x^{57} &&+3x^{56} &&-2x^{55}&&-10x^{54}\\ &-3x^{53} &&-2x^{52} &&+6x^{51} &&+6x^{50}&&+x^{49} &&+9x^{48} &&-3x^{47} &&-7x^{46}&&-8x^{45}\\ &-8x^{44} &&+10x^{43}&&+6x^{42} &&+8x^{41}&&-5x^{40}&&-12x^{39}&&+7x^{38} &&-7x^{37}&&+7x^{36}\\ &+x^{35} &&-3x^{34} &&+10x^{33}&&+x^{32} &&-6x^{31}&&-2x^{30} &&-10x^{29}&&-3x^{28}&&+2x^{27}\\ &+9x^{26} &&-3x^{25} &&+14x^{24}&&-8x^{23}&& &&-7x^{21} &&+9x^{20} &&+3x^{19}&&-4x^{18}\\ &-10x^{17} &&-7x^{16} &&+12x^{15}&&+7x^{14}&&+2x^{13}&&-12x^{12}&&-4x^{11} &&-2x^{10}&&+5x^9\\ & &&+x^7 &&-7x^6 &&+7x^5 &&-4x^4 &&+12x^3 &&-6x^2 &&+3x &&-6\\ &= 0. \end{align}</math>
« Désintégration audioactive »
John Conway qualifia initialement cette suite de « désintégration audioactive » (Modèle:Lang en anglais), un jeu de mots sur la désintégration radioactive, en remarquant le comportement des différents termes de la suite.
Dans son théorème cosmologique<ref name=":0" />, il démontra qu'à partir d'un certain point, presque tous les termes de la suite peuvent être décomposés en 92 sous-termes (nommés éléments, par analogie avec les éléments chimiques) qui se décomposent au terme suivant en un certain nombre d'autres éléments.
Par exemple, l'élément le plus simple, nommé hydrogène, est la séquence <math>22</math> qui donne elle-même au terme suivant. La séquence <math>3113322112</math> est dénommée manganèse ; au terme suivant, elle donne <math>1321232221112</math> qui se décompose en les séquences prométhium (<math>132</math>) et sodium (<math>123222112</math>).
Il a été montré que si l'on débute la suite par le terme uranium <math>3</math>, les 91 autres éléments seront apparus dans un terme ou un autre au bout de 91 itérations. Cette suite porte d'ailleurs en anglais le nom de Conway's sequence.
Dans la littérature
Bernard Werber a repris cette suite dans ses œuvres Les fourmis et dans L'Encyclopédie du savoir relatif et absolu<ref>Modèle:Youtube</ref>.
Références
Modèle:Traduction/Référence Modèle:Références
Annexes
Articles connexes
Liens externes
- {{#invoke:Langue|indicationDeLangue}} Look and Say sequence: describe the previous term! (method A - initial term is 1) : Modèle:OEIS
- Modèle:MathWorld
- {{#invoke:Langue|indicationDeLangue}} Henry Bottomley, « Evolution of Conway's 92 Look and Say audioactive elements » : une compilation des 92 éléments « audioactifs » de la suite
- Des algorithmes de générations en différents langages sur Rosetta Code
