Suite de Kolakoski

En mathématiques, la suite de Kolakoski, nommée d'après William Kolakoski (en), qui l'a étudiée en 1965[1]^,[2], est une suite infinie de symboles 1 et 2 qui est son propre codage par plages[3].

Visualisation sous forme de spirale des termes 3 à 50 de la séquence de Kolakoski.

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)

On code alternativement la longueur des plages de 1 et de 2 : 1 1, 2 2, 2 1, 1 2, 1 1, ...

Chaque symbole apparaît dans une « plage » d'un ou deux termes consécutifs, et la séquence des longueurs de ces plages redonne la même suite ; c'est la seule suite 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].

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é la constante de Kolakoski[10].

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).

(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.
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,‎ 1939, p. 453-466 (JSTOR 1989933).
(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.
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 (en), 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

Article connexe

Suite de Conway

Liens externes

Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[Kolakoski1965-1] (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.

[2] 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,‎ 1939, p. 453-466 (JSTOR 1989933).

[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] Integer Sequences and Arrays.

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

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

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

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

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