Suite de Kolakoski

En mathématiques, la suite de Kolakoski (ou suite d'Oldenburger-Kolakoski, apparaissant dès 1939 dans^[1]), proposée et étudiée par William Kolakoski (en) en 1965^[2], est une suite autoréférente infinie de symboles 1 et 2 qui est son propre codage par plages^[3].

Définition

Les premiers termes de la suite sont :

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1, ... (suite A000002 de l'OEIS)

Chaque symbole apparaît dans une « plage » d'un ou deux termes consécutifs et si l'on regroupe les termes par plages de 1 et de 2 :

(1),(2,2),(1,1),(2),(1),(2,2),(1),...,

la suite formée des longueurs successives de ces plages redonne la suite de départ : 1,2,2,1,1,2,1,... ; c'est la seule suite à deux symboles 1 et 2 ayant cette propriété et commençant par un 1^[3]^,^[4].

Propriétés

Un nombre important de questions peuvent se poser sur la suite de Kolakoski et sur les facteurs (i.e. plages de lettres consécutives) de cette suite :

le langage des facteurs est-il récurrent ? (autrement dit, est-ce que chaque facteur apparaissant à un endroit apparaît en fait une infinité de fois ?)
le langage des facteurs est-il stable sous image miroir ? (est-ce qu'en inversant le sens de lecture des facteurs, le langage reste inchangé ?)
le langage des facteurs est-il stable sous complétion ? (est-ce que si on prend tous les mots du langage et qu'on inverse les chiffres 1 et 2, le langage reste inchangé ?)

Des résultats liant les conjectures sur ces propriétés sont développés dans ^[5].

Il est raisonnable de penser que la densité asymptotique de chaque symbole est 1/2, mais cette conjecture reste non démontrée^[6]. Václav Chvátal a montré que la densité supérieure des 1 est inférieure à 0,50084 en 1993^[7] et le meilleur résultat dans cette direction est une borne de 0,50008^[8].

Il est remarquable que pour l'unique suite infinie de symboles 1 et 3 débutant à 1 et qui est son propre codage par plages, qui a pour premiers termes : 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3,... , on sait calculer exactement la fréquence du chiffre 3 (égale environ à 0,6) qui est un nombre algébrique de degré 3, ce qui est une conséquence du fait que cette suite est obtenue à partir d'un mot morphique sur un alphabet à 3 lettres ; voir la suite A064353 de l'OEIS. Plus généralement, le cas de figure le plus simple à étudier correspond aux suites engendrées par deux chiffres de même parité.

La suite de Kolakoski a également été remarquée par des informaticiens. Ainsi, Stephen Wolfram la décrit en relation avec l'étude des systèmes de tague cycliques^[9]^,^[10].

Remplaçant les 1 par des 0, les 2 par des 1, on peut interpréter la suite comme le développement d'un réel en base 2 ; ce réel est parfois encore appelé constante de Kolakoski^[11].

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Kolakoski sequence » (voir la liste des auteurs).

↑ Rufus Oldenburger, « Exponent Trajectories in Symbolic Dynamics », Transactions of the American Mathematical Society, vol. 46, n^o 3,‎ novembre 1939, p. 453 (ISSN 0002-9947, DOI 10.2307/1989933, lire en ligne, consulté le 22 août 2025)
↑ (en) William Kolakoski, « Self-generating runs, Problem 5304 », Am. Math. Monthly, vol. 72,‎ 1965, p. 674 ; pour une solution partielle, voir (en) Necdet Üçoluk, « Self Generating Runs », Am. Math. Monthly, vol. 73,‎ 1966, p. 681-682.
(en) N. Pytheas Fogg, Valérie Berthé (éditeur), Sébastien Ferenczi (éditeur), Christian Mauduit (éditeur) et A. Siegel (éditeur), Substitutions in dynamics, arithmetics and combinatorics, Berlin, Springer-Verlag, coll. « Lecture Notes in Mathematics », 2002 (1^re éd. 1794), 402 p. (ISBN 3-540-44141-7, zbMATH 1014.11015), p. 93.
↑ Plus précisément, on associe à la suite $u_{n}$ (formée de 1 et de 2) la suite $v_{n}$ qui compte la longueur des plages de $u_{n}$ (autrement dit, si $v_{n}=1$ correspond à la plage $u_{N}=2$ , mettons, c'est que $u_{N-1}=u_{N+1}=1$ , de même, si $v_{n}=2$ correspond à la plage $u_{N}=u_{N+1}=2$ , c'est que $u_{N-1}=u_{N+2}=1$ , et dans tous les cas, $v_{n+1}$ correspondra à la plage suivante, débutant à $u_{N+1}$ ou $u_{N+2}$ respectivement. La suite de Kolakoski est la seule suite pour laquelle les deux suites $u_{n}$ et $v_{n}$ sont identiques.
↑ Alessandro Della Corte, « Kolakoski sequence: links between recurrence, symmetry and limit density », Open Journal of Discrete Applied Mathematics, vol. 4, n^o 1,‎ 20 avril 2021, p. 29–44 (ISSN 2617-9679 et 2617-9687, DOI 10.30538/psrp-odam2021.0052, lire en ligne, consulté le 22 août 2025)
↑ Integer Sequences and Arrays.
↑ (en) Vašek Chvátal, Notes on the Kolakoski Sequence, DIMACS Technical Report 93-84, décembre 1993.
↑ M. Rao, « Trucs et bidules sur la séquence de Kolakoski », 2012.
↑ Ainsi nommés en référence au jeu du loup, tag game en anglais.
↑ A New Kind of Science, p. 895.
↑ Voir la suite A118270 de l'OEIS.

Voir aussi

Bibliographie

(en) Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences : Theory, Applications, Generalizations, Cambridge University Press, 2003, 571 p. (ISBN 978-0-521-82332-6, zbMATH 1086.11015, lire en ligne), p. 337
(en) F. M. Dekking, « What is the long range order in the Kolakoski sequence? », dans R. V. Moody, Proceedings of the NATO Advanced Study Institute (Waterloo, 1995), Dordrecht, Netherlands, Kluwer, 1997, p. 115-125
(en) J. M. Fédou et G. Fici, « Some remarks on differentiable sequences and recursivity », J. Integer Sequ., vol. 13, n^o 3, 2010, article 10.3.2
(en) Abdallah Hammam, « Some New Formulas for the Kolakoski sequence A000002 », Turkish Journal of Analysis and Number Theory, vol. 4 , n^o 3, 2016, p. 54-59, lire en ligne DOI 10.12691/tjant-4-3-1
(en) M. S. Keane (de), « Ergodic theory and subshifts of finite type », dans T. Bedford et M. Keane, Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Oxford, England, Oxford University Press, 1991, p. 35-70
(en) J. C. Lagarias, « Number theory and dynamical systems », dans S. A. Burr (en), The Unreasonable Effectiveness of Number Theory, Providence, RI, AMS, 1992, p. 35-72.
(en) G. Paun (en) et A. Salomaa, « Self-reading sequences », Am. Math. Monthly, vol. 103, 1996, p.166-168
(en) Jeffrey Shallit, « Number theory and formal languages », dans Dennis A. Hejhal, Joel Friedman, Martin C. Gutzwiller et Andrew M. Odlyzko, Emerging Applications of Number Theory, Springer-Verlag, coll. « The IMA Volumes in Mathematics and its Applications » (n^o 109), 1999 (ISBN 0-387-98824-6, lire en ligne), p. 547-570
(en) Bertran Steinsky, « A recursive formula for the Kolakoski sequence A000002 », J. Integer Sequ., vol. 9, 2006, article 06.3.7

Articles connexes

Suite de Conway
Suite de Golomb (qui est aussi égale à la suite formée des longueurs successive de ses plages)

Liens externes

(en) Eric W. Weisstein, « Kolakoski Sequence », sur MathWorld
(en) « Kolakoski Constant to 25000 digits as computed by Olivier Gerard in April 1998 »

Arithmétique et théorie des nombres

[1] Rufus Oldenburger, « Exponent Trajectories in Symbolic Dynamics », Transactions of the American Mathematical Society, vol. 46, n^o 3,‎ novembre 1939, p. 453 (ISSN 0002-9947, DOI 10.2307/1989933, lire en ligne, consulté le 22 août 2025)

[Kolakoski1965-2] (en) William Kolakoski, « Self-generating runs, Problem 5304 », Am. Math. Monthly, vol. 72,‎ 1965, p. 674 ; pour une solution partielle, voir (en) Necdet Üçoluk, « Self Generating Runs », Am. Math. Monthly, vol. 73,‎ 1966, p. 681-682.

[PF93-3] (en) N. Pytheas Fogg, Valérie Berthé (éditeur), Sébastien Ferenczi (éditeur), Christian Mauduit (éditeur) et A. Siegel (éditeur), Substitutions in dynamics, arithmetics and combinatorics, Berlin, Springer-Verlag, coll. « Lecture Notes in Mathematics », 2002 (1^re éd. 1794), 402 p. (ISBN 3-540-44141-7, zbMATH 1014.11015), p. 93.

[4] Plus précisément, on associe à la suite $u_{n}$ (formée de 1 et de 2) la suite $v_{n}$ qui compte la longueur des plages de $u_{n}$ (autrement dit, si $v_{n}=1$ correspond à la plage $u_{N}=2$ , mettons, c'est que $u_{N-1}=u_{N+1}=1$ , de même, si $v_{n}=2$ correspond à la plage $u_{N}=u_{N+1}=2$ , c'est que $u_{N-1}=u_{N+2}=1$ , et dans tous les cas, $v_{n+1}$ correspondra à la plage suivante, débutant à $u_{N+1}$ ou $u_{N+2}$ respectivement. La suite de Kolakoski est la seule suite pour laquelle les deux suites $u_{n}$ et $v_{n}$ sont identiques.

[5] Alessandro Della Corte, « Kolakoski sequence: links between recurrence, symmetry and limit density », Open Journal of Discrete Applied Mathematics, vol. 4, n^o 1,‎ 20 avril 2021, p. 29–44 (ISSN 2617-9679 et 2617-9687, DOI 10.30538/psrp-odam2021.0052, lire en ligne, consulté le 22 août 2025)

[6] Integer Sequences and Arrays.

[7] (en) Vašek Chvátal, Notes on the Kolakoski Sequence, DIMACS Technical Report 93-84, décembre 1993.

[8] M. Rao, « Trucs et bidules sur la séquence de Kolakoski », 2012.

[9] Ainsi nommés en référence au jeu du loup, tag game en anglais.

[10] A New Kind of Science, p. 895.

[11] Voir la suite A118270 de l'OEIS.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]