vignette|Visualisation sous forme de spirale des termes 3 à 50 de la suite de Kolakoski.
En mathématiques, la suite de Kolakoski (ou suite d'Oldenburger-Kolakoski, apparaissant dès 1939 dans un article de Rufus Oldenburger), proposée et étudiée par en 1965 ; pour une solution partielle, voir ., 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, ... (c'est la )
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.Plus précisément, on associe à la suite (formée de 1 et de 2) la suite qui compte la longueur des plages de (autrement dit, si correspond à la plage , mettons, c'est que , de même, si correspond à la plage , c'est que , et dans tous les cas, correspondra à la plage suivante, débutant à ou respectivement. La suite de Kolakoski est la seule suite pour laquelle les deux suites et sont identiques..
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 .
Il est raisonnable de penser que la densité asymptotique de chaque symbole est 1/2, mais cette conjecture reste non démontréeInteger Sequences and Arrays.. 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) 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 . 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 cycliquesAinsi nommés en référence au jeu du loup, tag game en anglais.A New Kind of Science, ..
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 KolakoskiVoir la ..
Notes et références
Voir aussi Bibliographie
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 J. M. Fédou et G. Fici, « Some remarks on differentiable sequences and recursivity », J. Integer Sequ., vol. 13, , 2010, article 10.3.2 Abdallah Hammam, « Some New Formulas for the Kolakoski sequence A000002 », Turkish Journal of Analysis and Number Theory, vol. 4 , , 2016, , lire en ligne , « 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 . et A. Salomaa, « Self-reading sequences », Am. Math. Monthly, vol. 103, 1996, p.166-168
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
Kolakoski Catégorie:Autoréférence