Une généralisation Kol(m, n, ..., p) de la suite de Kolakoski

Index général des suites Suite de Kolakowski

Présentation

On peut généraliser la construction du mot infini de Kolakoski K = 12112122122112... de la manière qui suit.

On se donne

Une suite finie m₀, m₁,..., m_p d'entiers naturels non nuls
Un ensemble A de symboles différents a₀, a₁,..., a_p
L'application f de A dans N^* qui associe à a_i l'entier m_i
La première lettre ou les premières lettres du mot M = Kol(m₁,..., m_p) à construire.

Le mot infini M = Kol(m₁,..., m_p) se construit alors de la manière suivante

Les premières lettres du mot M sont données. Seule la dernière lettre de ce préfixe détermine la suite à venir du mot.
En partant de la dernière lettre du préfixe et en lisant les unes après les autres les lettres x du mot M on détermine des blocs successifs de f(x) lettres identiques que l'on place à la droite du mot en construction.
Les lettres des blocs se suivent circulairement dans l'alphabet ordonné A.

Exemple détaillé Kol(1, 2, 3) et l'alphabet {a, b, c}
La liste ordonnée A est a, b, c. L'application de A dans N^* est a -> 1, b -> 2, c -> 3. La première lettre est a

Début : [a]
L'index [ ] parcourt le mot et pour l'instant il est sur la seule lettre connue du mot : '[a]'
Lorsque l'index est sur 'a' on écrit 1 lettre, s'il était sur 'b' on écrirait un groupe de deux lettres et s'il était sur une lettre 'c', on écrirait un groupe de trois lettres.
La dernière lettre écrite est 'a', celle qui suivra sera un 'b', on écrit donc un 'b', le nouveau mot est 'ab', l'index avance d'un cran et se place sur 'b'.
a[b] l'index est sur b, on écrit donc un groupe de deux lettres. Comme la dernière lettre du mot est b, on écrit la lettre suit 'b' dans l'alphabet, c'est 'c' (deux fois).
ab[c]c l'index est sur 'c', on écrit donc un groupe de 3 lettres
abc[c]aaa
abcc[a]aabbb
Kol(1, 2, 3) = abccaaabbbcabccaabbcccabbcccaaabcaabbcccaaabbbcaabbcccaaabbb...
Dans ce cas on peut préférer l'alphabet {1, 2, 3}, le mot obtenu s'écrit alors
Kol(1, 2, 3) = 123311122231233112233312233311123112233311122231122333111222...

Exemples

Cliquer les crochets [n] pour réaliser les exemples correspondants.
[0] {a, b, c},   [1] Kolakoski 1,   [2] Kolakoski 22,
[3] {1, 3},    [4] {1, 2, 3},   [5], {1, 2, 3, 4}   [6], {1, 2, 3, 5, 7, 11}
[7] 1 et 4,   [8] 1 et 6,   [9] 1 et 8,   [10] 1 et 10,
[11] 1 et 3,   [12] 1 et 5,   [13] 1 et 7,   [14] 1 et 9,
[15] 3 et 1,   [16] 3 et 5,   [17] 3 et 7,   [18] 3 et 9,
[19] 2 et 11,   [20] 4 et 11,   [21] 6 et 11,   [22] 8 et 11,
[23] et la [musique] obtenue.

Le « motif » recherché peut être un mot d'une ou plusieurs lettres ou une expression régulière de JavaScript (comme [12]{3} qui décrit aussi bien les deux mots '111' et '222').

Recherches de sous-chaînes

Pour rechercher cette suite de nombres dans la 'On-Line Encyclopedia of Integer Sequences', cliquez sur le bouton "Submit":

Explication de l'affichage

L'exemple [cliquer 1] donne pour la suite de Kolakoski les résultats suivants

           A(1) : 1 1 3 4 5 7 12 18 25 37 56 85 128 190 285 433 649 971 1453 ...
           A(2) : 0 1 1 2 4 7 10 15 24 37 56 84 126 191 288 429 643 965 1449 ...
           Diffs d(1) : 0 2 1 1 2 5 6 7 12 19 29 43 62 95 148 216 322 482 ...
           Diffs d(2) : 1 0 1 2 3 3 5 9 13 19 28 42 65 97 141 214 322 484 ...

           Somme A  =1 2 4 6 9 14 22 33 49 74 112 169 254 381 573 862 ...
           Diffs D  =1 2 2 3 5  8 11 16 25 38  57  85 127 192 289 430 ...
           Diffs D2 =1 0 1 2 3  3  5  9 13 19  28  42  65  97 141 214 ...

           Stats  : 9997 10003 
           121122121121221121121221221121221211211221221121
           221211221221121221221121122121121221221121121221
           1122122112122121122122121121122122112122121121122

Cette suite de Kolakovski a été construite, par étapes successives, comme ci-dessous :

                                    Somme A     A(1)      A(2)
         étape   suite              nb d'élts  nb de 1  nb de 2
           0     1                     1          1        0
           1     12                    2          1        1
           2     1211                  4          3        1
           3     121121                6          4        2
           4     121121221             9          5        4
           5     12112122122112       14          7        7

           La suite des différences d'ordre 1 
           des suites A(1) et A(2) sont d(1) et d(2)
           de la suite A est D
           La suite des différences d'ordre 2 de la suite A est D2

d(1)

Les éléments ajoutés à l'étape n permettent de déterminer ceux ajoutés à l'étape n+1.
En cliquant sur [Diff] on obtient les parties suivantes :

          1 -> 2 -> 11 -> 21 -> 221 -> 22112 ->...

[Affiche]

Suite de Kolakoski et liens.

Références, liens

Unsolved Problems and Rewards Integer Sequences and Arrays, Clark Kimberling U. Evansville

the On-Line Encyclopedia of Integer Sequences et en particulier Sequence A042942 et Sequence A000002

[arXiv] Kolakoski-(3,1) is a (deformed) model set Michael Baake, Bernd Sing (Univ. Greifswald) - Metric Geometry - Journal-ref: Canad. Math. Bull. 47, No. 2, 168--190 (2004)

[arXiv] Kolakoski-(2m,2n) are limit-periodic model sets Bernd Sing (Greifswald, Germany) - Mathematical Physics - J. Math. Phys. 44, No. 2, 899-912 (2003)

Les.mathématiques.net Hypothèse de Benoît pour l'alphabet {r, s}, r et s entiers de parités différentes.