In mathematics, the Kolakoski sequence (named after William Kolakoski) is an infinite sequence of symbols {1,2} which is its own run-length encoding.
Contents
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 the OEIS)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.
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.
Density
It seems plausible that the density of 1s is 1/2, but this conjecture remains unproved. Václav Chvátal has proved that the upper density of 1's is less than 0.50084. 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, 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.
History
Stephen Wolfram describes the Kolakoski sequence in connection with the history of cyclic tag systems.
Although Kolakowski wrote about the sequence in 1965, it previously appeared in a 1939 paper by Rufus Oldenburger.