Suite de Kolakoski
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Racine_carr%C3%A9e_bleue.svg/35px-Racine_carr%C3%A9e_bleue.svg.png)
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1d/Kolakoski_sequence_spiral.svg/220px-Kolakoski_sequence_spiral.svg.png)
En mathématiques, la suite de Kolakoski, proposée et étudiée par William Kolakoski (en) en 1965[1],[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
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 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[8],[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
- ↑ (en) William Kolakoski, « Self-generating runs, Problem 5304 », Am. Math. Monthly, vol. 72, , p. 674 ; pour une solution partielle, voir (en) Necdet Üçoluk, « Self Generating Runs », Am. Math. Monthly, vol. 73, , p. 681-682.
- ↑ Cependant, cette suite était déjà apparue dès 1939 dans (en) Rufus Oldenburger, « Exponent trajectories in symbolic dynamics », Trans. Amer. Math. Soc., vol. 46, , p. 453-466 (JSTOR 1989933).
- ↑ a et b (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 », (1re éd. 1794), 402 p. (ISBN 3-540-44141-7, zbMATH 1014.11015), p. 93.
- ↑ 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.
- ↑ (en) Vašek Chvátal, Notes on the Kolakoski Sequence, DIMACS Technical Report 93-84, .
- ↑ M. Rao, « Trucs et bidules sur la séquence de Kolakoski », .
- ↑ 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, , 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, no 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 , no 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, , 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 » (no 109), (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