Suite de Conway

La suite de Conway est une suite inventée en 1986 par le mathématicien John Horton Conway, initialement sous le nom de « suite audioactive ». 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.

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.

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 terme de la suite est proportionnel à λ, où $\lambda \approx 1,303577269$ 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 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.

Avec le PHP

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

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 #include using namespace std; template inline void echange(T & p1, T & p2) { T tmp; tmp = p1; p1 = p2; p2 = tmp; } int main() { list int_list; list int_list_temp; list * l = &int_list; list * ltemp = &int_list_temp; l->push_back(1); list ::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

import Data.List conway = iterate step [1] where step l = [f x | x <- group l, f <- [length,head] ] main = print . take 10 $ conway

En Perl5

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

ou depuis le shell:

perl -E '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()

En Prolog

conway(0,[1]). conway(N,R):- N>0, M is N-1, conway(M,L), conwayLigneSuivante(L,R). conwayLigneSuivante([],[]). conwayLigneSuivante([E],[1,E]). conwayLigneSuivante([E,E|L],[M,E|R]) :- conwayLigneSuivante([E|L],[N,E|R]), M is N+1. conwayLigneSuivante([E,F|L],[1,E|R]) :- dif(E,F), conwayLigneSuivante([F|L],R).

En Ocaml

open List let repetitions_au_debut l = let rec ajoute_repetition n x l = if l = [] then (n,x,l) else let (y::l1) = l in if x = y then ajoute_repetition (n+1) x l1 else (n,x,l) in let x::l1 = l in ajoute_repetition 1 x l1 let rec ligne_suivante l = if l = [] then [] else let (n,x,l1) = repetitions_au_debut l in n::x::(ligne_suivante l1) let conway n = let l = ref [1] in for i = 0 to n do iter (fun x -> print_string ((string_of_int x)^" ")) !l; print_string "\n\n"; l := ligne_suivante !l; done ;; conway 30;;

En Java

La classe ConwayTerm représente un terme donné de la suite. Sa méthode nextTerm calcule le terme suivant. Dans l'exemple ci-dessous, le premier terme est 1. Si l'on veut commencer avec 22, il faut un tableau de 2 bytes contenant chacun 2 et non un byte contenant 22 (new byte[] { 2,2 })

package fr.math.suite; import java.util.Arrays; public class ConwayTerm { private byte[] digits; /** * @param args */ public static void main(String[] args) { ConwayTerm term = new ConwayTerm(new byte[] { 1 }); // Premier terme de la suite:1 //Affiche les 25 premiers termes for (int i = 0; i < 25; i) { System.out.println("u(" + i + ")=" + term); term = term.nextTerm(); } } public ConwayTerm(byte[] digits) { this.digits = digits; } /** * calcule le terme suivant de la suite. */ public ConwayTerm nextTerm() { if (digits.length != 0) { byte count = 1; while ((count < digits.length && digits[0] == digits[count])) count; return concat(count, digits[0], new ConwayTerm(Arrays.copyOfRange( digits, count, digits.length)).nextTerm()); } else { return this; } } /** * Affiche les chiffres du terme de la suite */ public String toString() { StringBuffer buffer = new StringBuffer(); for (byte b : digits) buffer.append(b); return buffer.toString(); } private ConwayTerm concat(byte count, byte digit, ConwayTerm other) { byte[] result = new byte[2 + other.digits.length]; result[0] = count; result[1] = digit; for (int i = 0; i < other.digits.length; i++) result[i + 2] = other.digits[i]; return new ConwayTerm(result); } }