Kolakoski Sequence

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

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.

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.

It seems plausible that the density of 1's is 1/2, but this conjecture remains unproved. Chvátal has 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, Stephen Wolfram describes the Kolakoski sequence in connection with the history of cyclic tag systems.

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