Suite de conway


Suite de conway

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

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 :

X0 = 1

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

X1 = 11

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

X2 = 21

En poursuivant le procédé :

X3 = 1211
X4 = 111221
X5 = 312211
X6 = 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 ne terme de la suite est proportionnel à λn, où \lambda \approx 1,303577269 est un nombre algébrique de degré 71 nommé constante de Conway. Plus précisément, si on note Ln le nombre de chiffre du ne terme de la suite, alors :
\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.

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

x71x69 − 2x68x67 + 2x66 + 2x65 + x64x63x62x61x60x59 +
2x58 + 5x57 + 3x56 − 2x55 − 10x54 − 3x53 − 2x52 + 6x51 + 6x50 + x49 + 9x48 − 3x47
7x46 − 8x45 − 8x44 + 10x43 + 6x42 + 8x41 − 5x40 − 12x39 + 7x38 − 7x37 + 7x36 + x35
3x34 + 10x33 + x32 − 6x31 − 2x30 − 10x29 − 3x28 + 2x27 + 9x26 − 3x25 + 14x24 − 8x23
7x21 + 9x20 + 3x19 − 4x18 − 10x17 − 7x16 + 12x15 + 7x14 + 2x13 − 12x12 − 4x11
2x10 + 5x9 + x7 − 7x6 + 7x5 − 4x4 + 12x3 − 6x2 + 3x − 6 = 0
solutions du polynome de Conway sur le plan complexe.

« 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

La fonction conway() représentant la suite de Conway.

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

Liens externes

Bibliographie

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

Référence

  1. John H Conway, Richard K Guy, Le livre des nombres, Eyrolles (1998) - ISBN 2212036388
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Suite de Conway ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Suite de conway de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Suite de Conway — 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 …   Wikipédia en Français

  • Suite audioactive — 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… …   Wikipédia en Français

  • Suite de robinson — La suite de Robinson est une suite mathématique, une modification de la suite de Conway. Dans cette suite, un terme se détermine en comptant combien de fois chaque chiffre apparaît dans le terme précédent. Sommaire 1 Définition 2 Propriétés 3… …   Wikipédia en Français

  • Suite de Robinson — La suite de Robinson est une suite mathématique, une modification de la suite de Conway. Dans cette suite, un terme se détermine en comptant combien de fois chaque chiffre apparaît dans le terme précédent. Sommaire 1 Définition 2 Propriétés 3… …   Wikipédia en Français

  • Suite (mathématiques) — Pour les articles homonymes, voir Suite. En mathématiques, une suite[1] est une famille d éléments indexée par les entiers naturels. Une suite finie est une famille indexée par les entiers strictement positifs inférieurs ou égaux à un certain… …   Wikipédia en Français

  • Conway Tearle — Données clés Nom de naissance Frederick Lévy Naissance 17 mai 1878 New York, État de New York États Unis Nationalité …   Wikipédia en Français

  • Conway Rees — Pour les articles homonymes, voir Rees. Infobox Rugbyman Conway Rees …   Wikipédia en Français

  • Suite de Syracuse — Conjecture de Syracuse En mathématiques, on appelle suite de Syracuse une suite d entiers naturels définie de la manière suivante : On part d un nombre entier plus grand que zéro ; s’il est pair, on le divise par 2 ; s’il est… …   Wikipédia en Français

  • John Horton Conway — Pour les articles homonymes, voir Conway. John Horton Conway John Horton Conway en 2005 Naissance 26& …   Wikipédia en Français

  • Constante De Conway — La constante de Conway (notée λ) est la constante telle que , avec Ln le nombre de chiffres du n ième terme de la suite de Conway. John Conway a montré qu elle était la seule racine positive du polynôme de degré 71 suivant : x71 − x69 − 2x68 …   Wikipédia en Français