Suite de conway

La suite de Conway est une suite inventée en 1987 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.

Sommaire 1 Définition 2 Propriétés 2.1 « Désintégration audioactive » 2.2 Générer la Suite de Conway avec des langages de programmation 2.2.1 Avec le PHP 2.2.2 En C++ 2.2.3 En Haskell 2.2.4 En Perl6 2.2.5 En Python 3 Annexes 3.1 Articles connexes 3.2 Liens externes 3.3 Bibliographie 3.4 Référence

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 :

X₀ = 1

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

X₁ = 11

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

X₂ = 21

En poursuivant le procédé :

X₃ = 1211

X₄ = 111221

X₅ = 312211

X₆ = 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.

Propriétés

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 11 et les termes de rang pair par 21 (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 de chiffres du n^e terme de la suite est proportionnel à λⁿ, où est un nombre algébrique de degré 71 nommé constante de Conway. Plus précisément, si on note L_n le nombre de chiffre du n^e terme de la suite, alors :

Cette propriété reste vraie dans le cas général où le premier terme de la suite est choisi différent de 1.

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

x⁷¹ − x⁶⁹ − 2x⁶⁸ − x⁶⁷ + 2x⁶⁶ + 2x⁶⁵ + x⁶⁴ − x⁶³ − x⁶² − x⁶¹ − x⁶⁰ − x⁵⁹ +

2x⁵⁸ + 5x⁵⁷ + 3x⁵⁶ − 2x⁵⁵ − 10x⁵⁴ − 3x⁵³ − 2x⁵² + 6x⁵¹ + 6x⁵⁰ + x⁴⁹ + 9x⁴⁸ − 3x⁴⁷ −

7x⁴⁶ − 8x⁴⁵ − 8x⁴⁴ + 10x⁴³ + 6x⁴² + 8x⁴¹ − 5x⁴⁰ − 12x³⁹ + 7x³⁸ − 7x³⁷ + 7x³⁶ + x³⁵ −

3x³⁴ + 10x³³ + x³² − 6x³¹ − 2x³⁰ − 10x²⁹ − 3x²⁸ + 2x²⁷ + 9x²⁶ − 3x²⁵ + 14x²⁴ − 8x²³ −

7x²¹ + 9x²⁰ + 3x¹⁹ − 4x¹⁸ − 10x¹⁷ − 7x¹⁶ + 12x¹⁵ + 7x¹⁴ + 2x¹³ − 12x¹² − 4x¹¹ −

2x¹⁰ + 5x⁹ + x⁷ − 7x⁶ + 7x⁵ − 4x⁴ + 12x³ − 6x² + 3x − 6 = 0

« Désintégration audioactive »

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 terme de Conway's sequence.

Générer la Suite de Conway avec des langages de programmation

Avec le PHP

On peut très facilement avec une fonction récursive, ou avec les boucles créer la fonction conway() :

<?php
$a1 = array('1', '2', '3');
$a2 = array('a', 'b', 'c');
$b1 = array('bbb', 'aaa', 'cc', 'bb', 'aa', 'c', 'b', 'a');
$b2 = array('32', '31', '23', '22', '21', '13', '12', '11');

function conway($n, $str = '1', $i = 0) {
    // $n : la ligne de la suite de conway à afficher
    // $i est passé en paramètre lors de la récursivité (appel à la fonction même)
    // On rend globales les variables $a1, $a2, $b1 et $b2, pour ne pas avoir à les définir à chaque fois.
    global $a1, $a2, $b1, $b2;
    if($i < $n) {
        return conway($n, str_replace($b1, $b2, str_replace($a1, $a2, $str)), ++$i);
    }
    else {
        return $str;
    }
}
echo conway(3, $str = '1', $i = 0); 
// Execution : cela affichera 3 lignes de la suite ?>

En C++

Voici un bout de code écrit en C++ permettant d'afficher les n premières lignes de la suite de Conway. L'entier n est lu au clavier :

#include <iostream>
#include <list>
using namespace std;
template <typename T>
inline void echange(T & p1, T & p2)
{
	T tmp;
	tmp = p1;
	p1 = p2;
	p2 = tmp;
} 
 
int main()
{ 
	list <int> int_list;
	list <int> int_list_temp;

	list <int> * l	   = &int_list;
	list <int> * ltemp = &int_list_temp;

	l->push_back(1);

	list <int>::iterator iter;
	int temp = 0;
	int counter = 0;
	int n;

	cin >> n;

	cout << 1 << endl;

	for (int i = 1; i < n; ++i)
	{
		ltemp->clear();

		for (iter = l->begin(); iter != l->end(); counter = 0)
		{
			temp = *iter;
			++counter;
			++iter;

			while ((iter != l->end()) && (*iter == temp))
			{
				++counter;
				++iter;
			}

			cout << counter << temp;

			ltemp->push_back(counter);
			ltemp->push_back(temp);
		}

		cout << endl;
		
		echange(l, ltemp);
	}

	return 0;
}

En Haskell

 conway = iterate step [1] where
   step l = [f x | x <- group l, f <- [length,head] ]

En Perl6

   for ( $_=1;; ) { say; s/((.)\2*)/length($1).$2/xeg; }

En Python

 import itertools

 def conway():
     x = '1'
     while True:
         yield x
         nx = ''
         for item, grouper in itertools.groupby(x):
             nx += '%d%s' % (len(list(grouper)), item)
         x = nx

 suite = conway()
 for i in range(10):
     print suite.next()

Annexes

Articles connexes

• Suite de Robinson
• Run-length encoding
• Suite (mathématiques)

Liens externes

• (en) Encyclopédie électronique des suites entières : suite A005150
• (en) MathWorld : Look and Says Sequence
• (en) Evolution of Conway's 92 Look and Say audioactive elements : une compilation des 92 éléments « audioactifs » de la suite

Bibliographie

• John H Conway, Richard K Guy, Le livre des nombres, Eyrolles (1998) - ISBN 2212036388

Référence

• Portail des mathématiques