Kolakoski sequence

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, the Kolakoski sequence (named after William Kolakoski, who discussed it in 1965[1]) is an infinite sequence of symbols {1,2} which is its own run-length encoding.[2]

The initial terms of the sequence are:

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,… (sequence A000002 in OEIS)

Each symbol occurs in a "run" of either 1 or 2 consecutive terms, and writing down the lengths of these runs gives exactly the same sequence. It is the unique sequence with this property except for the same sequence with the initial 1 deleted.[2]

Algorithm[edit]

The sequence may be generated by an algorithm that, in the ith iteration, reads the value xi that has already been output as the ith value of the sequence (or, if no such value has been output yet, sets xi = i). Then, if i is odd, it outputs xi copies of the number 1, while if i is even, it outputs xi copies of the number 2. Thus, the first few steps of the algorithm are:

  1. The first value has not yet been output, so set x1 = 1, and output 1 copy of the number 1
  2. The second value has not yet been output, so set x2 = 2, and output 2 copies of the number 2
  3. The third value x3 was output as 2 in the second step, so output 2 copies of the number 1.
  4. The fourth value x4 was output as 1 in the third step, so output 1 copy of the number 2.

etc.

Density[edit]

It seems plausible that the density of 1s is 1/2, but this conjecture remains unproved.[3] Chvátal has proved that the upper density of 1's is less than 0.50084.[4]

History[edit]

Kolakoski's self-generating sequence has attracted the interest of computer scientists as well as mathematicians. For example, Stephen Wolfram describes the Kolakoski sequence in connection with the history of cyclic tag systems.[5]

Recently Jean Berstel and Srecko Brlek discovered that the Kolakoski sequence already appeared, before Kolakoski, in a 1939 paper of Rufus Oldenburger.

See also[edit]

Notes[edit]

  1. ^ William Kolakoski, Self-Generating Runs, Problem 5304, American Mathematical Monthly, vol. 72 (1965), p. 674
  2. ^ a b Pytheas Fogg (2002) p.93
  3. ^ Integer Sequences and Arrays
  4. ^ Notes on the Kolakoski Sequence, unpublished technical report
  5. ^ A New Kind of Science, p. 895

References[edit]

  • Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. p. 337. ISBN 978-0-521-82332-6. Zbl 1086.11015. 
  • Chvátal, Vašek (December 1993). Notes on the Kolakoski Sequence. DIMACS Technical Report 93-84. 
  • Dekking, F. M. (1997). "What Is the Long Range Order in the Kolakoski Sequence?". In Moody, R. V. Proceedings of the NATO Advanced Study Institute, Waterloo, ON, August 21-September 1, 1995. Dordrecht, Netherlands: Kluwer. pp. 115–125. 
  • Fedou, J. M.; Fici, G. (2010). "Some remarks on differentiable sequences and recursivity". Journal of Integer Sequences 13 (3). Article 10.3.2. 
  • Keane, M. S. (1991). "Ergodic Theory and Subshifts of Finite Type". In Bedford, T.; Keane, M. Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces. Oxford, England: Oxford University Press. pp. 35–70. .
  • Kolakoski, William (1965). "Problem 5304". American Mathematical Monthly 72: 674.  For a partial solution, see Üçoluk, Necdet (1966). "Self Generating Runs". American Mathematical Monthly 73: 681–682. 
  • Lagarias, J. C. (1992). "Number Theory and Dynamical Systems". In Burr, S. A.. The Unreasonable Effectiveness of Number Theory. Providence, RI: American Mathematical Society. pp. 35–72. 
  • Oldenburger, Rufus (1939). "Exponent trajectories in symbolic dynamics". Transactions of the American Mathematical Society 46: 453–466. doi:10.2307/1989933. 
  • Paun, G.; Salomaa, A. (1996). "Self-Reading Sequences". American Mathematical Monthly 103: 166–168. doi:10.2307/2975113. 
  • Fogg, N. Pytheas; Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, Anne, eds. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics 1794. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015. 
  • Shallit, Jeffrey (1999). "Number theory and formal languages". In Hejhal, Dennis A.; Friedman, Joel; Gutzwiller, Martin C.; Odlyzko, Andrew M.. Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15--26, 1996. The IMA volumes in mathematics and its applications 109. Springer-Verlag. pp. 547–570. ISBN 0-387-98824-6. 
  • Steinsky, Bertran (2006). "A Recursive Formula for the Kolakoski Sequence A000002". Journal of Integer Sequences 9. Article 06.3.7. 

External links[edit]