Suite de Conway

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La suite de Conway est une suite mathématique inventée en 1986 par le mathématicien John Horton Conway, initialement sous le nom de « suite audioactive »[1]. Elle est également connue sous le nom anglais de Look and Say (« regarder et dire »). Dans cette suite, un terme se détermine en annonçant les chiffres formant le terme précédent.

Définition[modifier | modifier le code]

Suite de Conway
Graphe représentant, en ordonnées, le nombre de chiffres du ne terme de la suite de Conway, avec n en abscisses, dans un repère semi-logarithmique. Chaque courbe correspond à un terme initial différent : 1 (bleu), 23 (rouge), 13 (violet), 312 (vert). Les courbes tendent vers une droite dont la pente correspond à la constante de Conway.

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 :

X_0 = 1

Ce terme comporte juste un « 1 ». Par conséquent, le terme suivant est :

X_1 = 11

Celui-ci est composé de deux « 1 » :

X_2 = 21

En poursuivant le procédé :

X_3 = 1211
X_4 = 111221
X_5 = 312211
X_6 = 13112221

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 ce n'est pas le cas.

Les 20 premiers termes[modifier | modifier le code]

Terme 1 1
2 11
3 21
4 1211
5 111221
6 312211
7 13112221
8 1113213211
9 31131211131221
10 13211311123113112211
11 11131221133112132113212221
12 3113112221232112111312211312113211
13 1321132132111213122112311311222113111221131221
14 11131221131211131231121113112221121321132132211331222113112211
15 311311222113111231131112132112311321322112111312211312111322212311322113212221
16 132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211
17 11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221
18 31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211
19 1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221
20 11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321

123113112221121113122113121113123112112322111213211322211312113211

Propriétés[modifier | modifier le code]

Les principales propriétés de cette suite sont :

  • 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.
  • Les termes de rang impair se terminent par 21 et les termes de rang pair par 11 (là encore à l'exception du terme initial).
  • En moyenne, les termes de la suite possèdent 50 % de chiffres 1, 31 % de 2 et 19 % de 3.
  • Le nombre L_n de chiffres du ne terme de la suite est équivalent à Cλn, où \scriptstyle \lambda \approx 1,303577269 est un nombre algébrique de degré 71 nommé constante de Conway, et C est une autre constante. En particulier :
    \lim_{n \to +\infty}\frac{L_{n+1}}{L_{n}} = \lambda
Cette propriété reste vraie dans le cas général 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 λ.
Racines du polynôme de Conway sur le plan complexe.

La constante de Conway est l'unique solution réelle positive de l'équation polynomiale suivante :

 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

On a l'approximation \lambda = 1,303577269\ldots

« Désintégration audioactive »[modifier | modifier le code]

John Conway qualifia initialement cette suite de « désintégration audioactive » (audioactive decay en anglais), un jeu de mots sur la désintégration radioactive, en remarquant le comportement des différents termes de la suite.

Il 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 22 qui donne elle-même au terme suivant. La séquence 3113322112 est dénommée manganèse ; au terme suivant, elle donne 132123222112 qui se décompose en les séquences prométhium (132) et sodium (123222112).

Il a été montré que si l'on débute la suite par le terme uranium 3, 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.

Algorithme[modifier | modifier le code]

L'algorithme de calcul suivant est écrit en Python :

def suivant ( s ):
    for n in xrange( len( s )) :
        if s[n] != s[0] :
            return str(n) + s[0] + suivant( s[n:] )
    return str(n+1) + s[0]
 
terme = '1'
for i in xrange( 1,15 ):
    print i,terme
    terme = suivant( terme )

Autre exemple en C#

static void Main(string[] args)
{
    String response = "1";
    Console.WriteLine("1");
 
    for (int i = 0; i < 10; i++)
        Console.WriteLine(ComputeSequence(ref response));
}
private static string ComputeSequence(ref string response)
{
    StringBuilder sb = new StringBuilder();
 
    for (int i = 0; i < response.Length; i++)
    {
         int count = 1;
         char s = response[i];
         while (i + 1 < response.Length && response[i] == response[i + 1])
         {
             count++;
             i++;
         }
         sb.Append(count);
         sb.Append(s);
     }
 
     response = sb.ToString();
     return response;
}

Autre exemple en Java

    public static void main(String[] args) {
	String terme = "1";
	for (int i = 1; i < 15; i++) {
	    System.out.println(i + " " + terme);
	    terme = lectureOrale(terme);
	}
    }
 
    private static String lectureOrale(String s) {
	int i = 0;
	for (i = 0; i < s.length(); i++) {
	    if (s.charAt(i) != s.charAt(0)) {
		return i + "" + s.charAt(0) + lectureOrale(s.substring(i));
	    }
	}
	return (i) + "" + s.charAt(0);
    }

Dans la littérature[modifier | modifier le code]

Bernard Werber a repris cette suite dans ses œuvres Les fourmis et dans L'Encyclopédie du savoir relatif et absolu[réf. souhaitée].

Références[modifier | modifier le code]

  1. (en) John H. Conway, « The Weird and Wonderful Chemistry of Audioactive Decay », Eureka, Université de Cambridge, no 46,‎ 1986, p. 5-18 (ISSN 0071-2248).

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Sur les autres projets Wikimedia :