Kolakoski sequence
In mathematics, the Kolakoski sequence (named after William Kolakoski) is an infinite sequence of symbols {1,2} which is its own run-length encoding.[1]
The initial terms of the sequence are:
Each symbol occurs in a "run" of either one or two 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.[1]
Algorithm
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:
- The first value has not yet been output, so set x1 = 1, and output 1 copy of the number 1
- The second value has not yet been output, so set x2 = 2, and output 2 copies of the number 2
- The third value x3 was output as 2 in the second step, so output 2 copies of the number 1.
- The fourth value x4 was output as 1 in the third step, so output 1 copy of the number 2.
etc.
This algorithm takes linear time, but because it needs to refer back to earlier positions in the sequence it needs to store the whole sequence, taking linear space. An alternative algorithm that generates multiple copies of the sequence at different speeds, with each copy of the sequence using the output of the previous copy to determine what to do at each step, can be used to generate the sequence in linear time and only logarithmic space.[2]
Density
It seems plausible that the density of 1s is 1/2, but this conjecture remains unproved.[3] Václav Chvátal has proved that the upper density of 1's is less than 0.50084.[4] Although calculations of the first 3×108 values of the sequence appeared to show its density converging to a value slightly different from 1/2,[5] later calculations that extended the sequence to its first 1013 values show the deviation from a density of 1/2 growing smaller, as one would expect if the limiting density actually is 1/2.[2]
History
Stephen Wolfram describes the Kolakoski sequence in connection with the history of cyclic tag systems.[6]
Although Kolakowski wrote about the sequence in 1965,[7] it previously appeared in a 1939 paper by Rufus Oldenburger.[8]
See also
Notes
- 1 2 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. p. 93. ISBN 3-540-44141-7. Zbl 1014.11015.
- 1 2 Nilsson, Johan (2012). "A space-efficient algorithm for calculating the digit distribution in the Kolakoski sequence" (PDF). Journal of Integer Sequences. 15 (6): Article 12.6.7, 13. MR 2954662.
- ↑ Kimberling, Clark. "Integer Sequences and Arrays". University of Evansville. Retrieved 2016-10-13.
- ↑ Chvátal, Vašek (December 1993). Notes on the Kolakoski Sequence. Technical Report 93-84. DIMACS.
- ↑ Steinsky, Bertran (2006). "A recursive formula for the Kolakoski sequence A000002" (PDF). Journal of Integer Sequences. 9 (3). Article 06.3.7. MR 2240857. Zbl 1104.11012.
- ↑ Wolfram, Stephen (2002). A New Kind of Science. Champaign, IL: Wolfram Media, Inc. p. 895. ISBN 1-57955-008-8. MR 1920418.
- ↑ 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. doi:10.2307/2314839.
- ↑ Oldenburger, Rufus (1939). "Exponent trajectories in symbolic dynamics". Transactions of the American Mathematical Society. 46: 453–466. doi:10.2307/198993. MR 0000352.
Further reading
- 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.
- 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.
- 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.
- Păun, Gheorghe; Salomaa, Arto (1996). "Self-Reading Sequences". American Mathematical Monthly. 103: 166–168. doi:10.2307/2975113. Zbl 0854.68082.
- 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. Zbl 0919.00047.