Kolakoski sequence

A Kolakoski sequence is a ``self-describing'' sequence $\{k_n\}_{k=0}^{\infty}$ of alternating blocks of 1's and 2's, given by the following rules:

• $k_0=1$ .¹
• $k_n$ is the length of the $(n+1)$ 'th block.

Thus, the sequence begins 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, ...

It is conjectured that the density of 1's in the sequence is 0.5. It is not known whether the 1's have a density; however, it is known that were this true, that density would be 0.5. It is also not known whether the sequence is a strongly recurrent sequence; this too would imply density 0.5.

Extensive computer experiments strongly support the conjecture. Furthermore, if $o_n$ is the number of 1's in the first $n$ elements, then it appears that $o_n = 0.5n + O(\log n)$ . Note for comparison that for a random sequence of 1's and 2's, the number of 1's in the first $n$ elements is with high probability $0.5n + O(\sqrt{n})$ .

To generate rapidly a large number of elements of the sequence, it is most efficient to build a heirarchy of generators for the sequence. If the conjecture is correct, then the depth of this heirarchy is only $O(\log n)$ to generate the first $n$ elements.

This is sequence A000002 in the Online Encyclopedia of Integer Sequences.

Footnotes

... .¹

Some sources start the sequence at $k_0=2$ , instead. This only has the effect of shifting the sequence by one position.