Suite de Kolakoski
En mathématiques, la suite de Kolakoski, proposée et étudiée par Modèle:Lien en 1965[1]Modèle:,[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, ... (Modèle: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]Modèle:,[4].
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[5]. Václav Chvátal a montré que la densité supérieure des 1 est inférieure à 0,50084 en 1993[6] et le meilleur résultat dans cette direction est une borne de 0,50008[7].
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 Modèle: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[8]Modèle:,[9].
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[10].
Notes et références
Modèle:Traduction/Référence Modèle:Références
Voir aussi
Bibliographie
- Modèle:Ouvrage
- Modèle: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
- Modèle:En J. M. Fédou et G. Fici, « Some remarks on differentiable sequences and recursivity », J. Integer Sequ., vol. 13, Modèle:N°, 2010, article 10.3.2
- Modèle:En Abdallah Hammam, « Some New Formulas for the Kolakoski sequence A000002 », Turkish Journal of Analysis and Number Theory, vol. 4 , Modèle:N°, 2016, Modèle:P., lire en ligne Modèle:DOI
- Modèle:En Modèle:Lien, « 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
- Modèle:Chapitre.
- Modèle:En Modèle:Lien et A. Salomaa, « Self-reading sequences », Am. Math. Monthly, vol. 103, 1996, p.166-168
- Modèle:Chapitre
- Modèle: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
- ↑ Modèle:Article ; pour une solution partielle, voir Modèle:Article.
- ↑ Cependant, cette suite était déjà apparue dès 1939 dans Modèle:Article.
- ↑ 3,0 et 3,1 Modèle:Ouvrage.
- ↑ 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.
- ↑ Integer Sequences and Arrays.
- ↑ Modèle:Ouvrage.
- ↑ Modèle:Lien web.
- ↑ Ainsi nommés en référence au jeu du loup, tag game en anglais.
- ↑ A New Kind of Science, Modèle:P..
- ↑ Voir la Modèle:OEIS.