Kolakoski sequence

In mathematics, the Kolakoski sequence (named after William Kolakoski, who introduced it in 1965[1]) is an infinite list that begins with:

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)

The rules for generating this sequence are as follows:

1) The only numbers allowed are 1 and 2
2) Each number tells us how many numbers to append to the sequence
2a) 1 tells us to append one more number
2b) 2 tells us to append two more numbers
3) We can have no more than two of the same number in sequence
3a) This is because if we write 222 that means that somewhere in the sequence it told us to append 3 twos, but the only numbers allowed are 1 and 2
4) Every time we "read" a new number, we alternate between writing 1 and 2
5) A0=1

This is an example of a self-generating sequence, with the first term as 1. Each individual number describes how many numbers to write next. This is called the run of the numbers. To start the sequence we have to write one 2 after the 1 because the 1 tells us to write one number, and because our initial condition "wrote" the one we must alternate by writing the 2. This gives us as our sequence so far (1 2). Next, The 2 tells us that the length, or the run, of the next set of numbers must be 2, but we cannot have any more than two ones or two twos in sequence because that would mean that the sequence told us to write three 2's, which would mean a 3 would have to be in the sequence, which is not allowed. Therefore, we must write 2 1. This gives us our sequence so far (1 2 2 1). The next number in the list is a 2, so we must write two numbers. The next two numbers that we should write is a 1; however, we cannot write three 1's in a row, so we must append 1 2 to the sequence. This gives us our sequence so far (1 2 2 1 1 2). The fourth number in the list is a 1. As we wrote a 2 last we write a 1 now. This gives us our sequence so far (1 2 2 1 1 2 1). The fifth number in the sequence is a 1. As we wrote a 1 before, we must write a 2 now. This gives us our sequence so far (1 2 2 1 1 2 1 2). This continues on. Another explanation for the generation of the Kolakoski sequence is indicated here:

(1) write 1; read it as the number of 1's to write before switching to 2;

(2) write 2; read it as the number of 2's to write before switching back to 1;

(3) so far... 1,2,2; read the new 2 as the number of 1's to write;

(4) so far... 1,2,2,1,1; read the new 1,1 as the number of 2's and then 1's to write;

(5) so far... 1,2,2,1,1,2,1; continue generating forever.

To truly understand how the sequence is generated, follow either of the two examples above and write out the first few terms.

It seems plausible that the density of 1's is 1/2, but this conjecture remains unproved. This and related simply stated unsolved problems are presented at Integer Sequences and Arrays. In the unpublished technical report Notes on the Kolakoski Sequence, Chvátal proved that the upper density of 1's is less than 0.50084.

Kolakoski's self-generating sequence has attracted the interest of computer scientists as well as mathematicians. For example, in A New Kind of Science, p. 895, Stephen Wolfram describes the Kolakoski sequence in connection with the history of cyclic tag systems.
References

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 337.
Vašek Chvátal, "Notes on the Kolakoski Sequence", DIMACS Technical Report 93-84, December 1993.
F. M. Dekking, "What Is the Long Range Order in the Kolakoski Sequence?" In Proceedings of the NATO Advanced Study Institute held in Waterloo, ON, August 21-September 1, 1995 (dd. R. V. Moody). Dordrecht, Netherlands: Kluwer, pp. 115-125, 1997.
M. S. Keane, "Ergodic Theory and Subshifts of Finite Type." In Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces (ed. T. Bedford and M. Keane). Oxford, England: Oxford University Press, pp. 35-70, 1991.
William Kolakoski, proposal 5304, American Mathematical Monthly 72 (1965), 674; for a partial solution, see "Self Generating Runs," by Necdet Üçoluk, Amer. Math. Mon. 73 (1966), 681-2.
J. C. Lagarias, "Number Theory and Dynamical Systems." In The Unreasonable Effectiveness of Number Theory (ed. S. A. Burr). Providence, RI: Amer. Math. Soc., pp. 35-72, 1992.
G. Paun and A. Salomaa, "Self-Reading Sequences." Amer. Math. Monthly 103, 166-168, 1996.
Bertran Steinsky, "A Recursive Formula for the Kolakoski Sequence A000002," Journal of Integer Sequences 9 (2006) Article 06.3.7.
J. M. Fedou and G. Fici, "Some remarks on differentiable sequences and recursivity", "Journal of Integer Sequences" 13(3) (2010) Article 10.3.2.

^ William Kolakoski, Self-Generating Runs, Problem 5304, American Mathematical Monthly, vol. 72 (1965), p. 674

External links

Kolakoski Sequence
Kolakoski Constant to 25000 Digits.