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 This is an example of a selfgenerating 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 selfgenerating 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. J.P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 337. ^ William Kolakoski, SelfGenerating Runs, Problem 5304, American Mathematical Monthly, vol. 72 (1965), p. 674 External links Kolakoski Sequence Retrieved from "http://en.wikipedia.org/"


