constante de Thue-Morse, constante de parité

NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 03/07/2016 Orientation générale DicoMot Math Atlas Références M'écrire Barre de recherche DicoCulture Index alphabétique
	CONSTANTES
Débutants Général	C				Glossaire Général
INDEX Nombres	Pi = 3,14…	Exp (1) = e = 2,718…	Thue-Morse	Liouville
		Sommaire de cette page >>> Soyons juste >>> Comptage binaire >>> Approche >>> Suites de Thue-Morse >>> Construction >>> Propriétés >>> Autres types >>> Constante de Thue-Morse >>> Calcul >>> Applications

Thue-Morse

ou Prouhet-Thue-Morse

Suite, nombre, constante

Suites binaires aux propriétés particulières de non répétitivité.

Cette suite est connue sous le nom de Thue-Morse. C'est pourtant Eugène Prouhet (1817-1867) qui l'utilise en 1851 en combinatoire.

Axel Thue (1863-1922) la redécouvre en 1912; de même que Marston Morse (1892-1977) en 1921.

Anglais: Thue-Morse sequence , also called the Thue-Morse infinite word.

Voir Mathématiciens des années 1800

Soyons juste

Deux individus A et B jouent à un jeu.
Le sort décide que A joue avant B:	AB
Pour la partie suivante, B exige de commencer:	ABBA
En poursuivant le jeu, il semble qu'il soit équitable d'inverser à nouveau l'ordre:	ABBA BAAB
Ainsi de suite si le jeu continue.

Anglais: The fairest sharing sequence

Comptage binaire

N₁₀	N₂	Qté de 1	Pair / Impair
0	0	0	P
1	1	1	I
2	10	1	I
3	11	2	P
4	100	1	I
5	101	2	P
6	110	2	P
7	111	3	I

La suite PIIP IPPI est identique à celle en ABBA BAAB.

Approche – Construction
	Binaire	Décimal	Décimal * pour 0, binaire
Démarrer avec le 0	0	0	0
Concaténer avec le complément binaire	0 1	1	0,25
Recommencer avec le nombre obtenu	01 10	6	0,375
Encore …	0110 1001	105	0,4101562500
Notez: ce premier nombre binaire est palindrome. Mais, le suivant ne l'est pas.	01101001 10010110	27 030	0,4124450684
	0110100110010110 1001011001101001	1 771 476 585	0,4124540335

* Voir Explication de la dernière colonne

Suites de Thue-Morse
Définition Suite binaire dans laquelle on ne trouve jamais trois fois de suite la même séquence. Pas trois 0, pas trois 01, pas trois 0011, etc. Suite classique de Thue-Morse … 0110100110010110 1001011001101001 …	Cette suite a été construite dans le cadre de la recherche de suites totalement désordonnées. Celle-ci l'est dans sa forme, pas dans sa construction. La construction étant d'ailleurs merveilleusement simple! => Faible complexité algorithmique
Définition alternative La suite peut être définie par la relation de récurrence suivante: La dernière relation étant relative à du binaire, elle peut aussi s'écrire: t_2n+1 = non (t_n).	Exemple avec huit itérations

Construction

Méthode 1 :

Remplacement

Commencez par

0 1

Remplacez 0 par 01

Et 1 par 10

0 1 1 0

Recommencez

0 1 1 0 1 0 0 1

Méthode 2 :

Complément

Commencez par

Ajoutez le complément

0 1

Recommencez

0 1 1 0

…

0 1 1 0 1 0 0 1

Méthode 3 :

Comptage binaire

Compter en binaire

0 1 2 3 4 5 6 7 8 …

0 1 10 11 100 101 110 111 1000 …

Somme des chiffres

0 1 1 2 1 2 2 3 1

Modulo 2

0 1 1 0 1 0 0 1 1

Méthode 4 :

Construction rapide

(copier – coller)

On remplace les 0 et 1 par des dessins plus facile à visualiser

1	Soit la ligne n	¨§§¨
2	Recopier (cf. méthode 2 du complément)	¨§§¨	…
3	Prendre la 2^e moitié de la ligne	¨§§¨	§¨
4	Ajouter la 1ère moitié	¨§§¨	§¨¨§

Construction rapide jusqu'à la 7^e génération

Voir Nombre 0110

Propriétés

La taille de la séquence grandit très, très vite.

Cette suite ne présente aucune périodicité:

Elle est apériodique et même … aléatoire;

Il n'y a jamais plus de 2 termes adjacents identiques;

Ne contient aucun groupes de trois fois le mème chiffre;

Ne contient aucun motif en XYXYX avec X= {0 ou 1} et Y = {toute suite de 0 et de 1).

Elle est autosimilaire

La structure générale d'une ligne à la suivante est de la forme:

1	2
idem		2	1

En sélectionnant une seule partie de la séquence, il est possible de la reproduire entièrement;

En prenant un bloc de n termes sur deux, il est également possible de la reproduire entièrement.

Voir Autosimilarité et fractales

Autres Types

Autre tentative pour chercher à remplir les conditions de la définition

Chercher un nombre transcendant, ne comportant pas de séquences répétitives comme = 1,4142135... non solution d'une équation polynomiale à coefficients entiers.

Exemple

est solution de X² – 2 = 0 et n'est pas transcendant.

Les deux plus connus sont

la constante "pi" et "e" (exponentielle)

Là aussi, échec car il y a un contre-exemple de nombres transcendants dont la règle de construction est simple. Donc, la suite n'est pas désordonnée.

Construction d'un transcendant

Placez un 0 entre deux 1, puis deux 0 entre deux 1, puis quatre, etc.

010100100001000000001

Liouville montra que ce nombre est transcendant en 1844, bien avant que soit démontrée la transcendance de pi ou e.

Constante de THUE-MORSE (ou constante de parité)

Le nombre binaire (B) formé selon la méthode Thue-Morse est prolongé jusqu'à l'infini.

On le transforme en une fraction en le précédent par 0,B

Puis ce nombre binaire est converti en décimal

*Base 2*	0,01101001100101101001011001101001…
*Base 10*	0,412 454 033 650 …

Calcul

Début du calcul (15 itérations)

Voir Nombre 0,412 …

Application des suites de Thue-Morse

Somme des entiers signés

Une application originale consiste à écrire la suite des nombres entiers affectés d'un signe suivant la suite de Thue-Morse.

On peut montrer que ces égalités sont généralisables et qu'on peut les construire en s'appuyant sur les suites de Morse.

1 + 4 + 6 + 7 =	2 + 3 + 5 + 8	= 18
1² + 4² + 6² + 7² =	2² + 3² + 5² + 8²	= 102

Autre écriture avec signe selon Thue-Morse

S8 = 1² – 2² – 3² + 4² – 5² + 6² + 7² – 8² = 0

Cette manière de voir est décrite ci-dessous pour les suites de k nombres signés.

La somme des entiers signés est égale à 0 et pour certaines suites la somme des carrés, des cubes et … est aussi égale à 0.

Entier

Carrés

Cubes

S4 = [1, -2, -3, 4]

S8 = [1, -2, -3, 4, -5, 6, 7, -8]

S12 = [1, -2, -3, 4, -5, 6, 7, -8, -9, 10, 11, -12]

S16 = [1, -2, -3, 4, -5, 6, 7, -8, -9, 10, 11, -12, 13, -14, -15, 16]

S20 = [1, -2, -3, 4, -5, 6, 7, -8, -9, 10, 11, -12, 13, -14, -15, 16, -17, 18, 19, -20]

S24 = [1, -2, -3, 4, -5, 6, 7, -8, -9, 10, 11, -12, 13, -14, -15, 16, -17, 18, 19, -20, 21, -22, -23, 24]

S28 = [1, -2, -3, 4, -5, 6, 7, -8, -9, 10, 11, -12, 13, -14, -15, 16, -17, 18, 19, -20, 21, -22, -23, 24, 25, -26, -27, 28]

S32= [1, -2, -3, 4, -5, 6, 7, -8, -9, 10, 11, -12, 13, -14, -15, 16, -17, 18, 19, -20, 21, -22, -23, 24, 25, -26, -27, 28, -29, 30, 31, -32]

Toutes les sommes Sk indiquée dans le tableau sont égales à 0 lorsqu'on somme les entiers signés ou les puissances indiquées signées.

Cas de S256

La liste des nombres signés est la suivante:

Les sommes de ces nombres jusqu'à la puissance 8 sont nulles.

Somme Sk et valeur nulle pour les puissances indiqués

Cas de S32 avec sommes nulles jusqu'à la puissance 4

Généralisation

On peut séparer les entiers compris entre 1 et 2m en deux classes A et B comportant le même nombre d'éléments de façon que la puissance k^ième des éléments de A soit égale à la puissance k^ième des éléments de B, pour tout k < m

On peut encore généraliser à n classes pour les entiers compris entre 1 et nm. Les mêmes égalités sont vérifiées pour les n classes formées.

Démonstration par E. Prouhet – 1851 – Mathématicien français

Suite	Constantes Somme des entiers, puissances, … Additions multipuissantes
Voir	Constantes Poussière de Cantor Commentaire en lettres Fractions continues Théorèmes Identités Suite de Champernowne Suite de Thue-Morse
DicoNombre	Nombre 0,412…
Sites	Le problème de Prouhet (et la suite de Thue-Morse) – Michel Rigo – 2012 – 67 pages pdf (diaporama) OEIS A010060 - Thue-Morse sequence Suite de Prouhet-Thue-Morse – Wikipédia Thue–Morse sequence – Wikipedia – Illustrations Thue–Morse sequence – Wolfram MathWorld – La théorie
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Nombre/Thue.htm