Suite de Kolakoski

En mathématiques, la suite de Kolakoski, proposée et étudiée par William Kolakoski (en) en 1965^,, est une suite autoréférente infinie de symboles 1 et 2 qui est son propre codage par plages.

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^,.

Propriétés

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

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) ; voir la suite A064353 de l'OEIS.

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^,.

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.

Notes et références

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