Kolakoski sequence

A Kolakoski sequence is a “self-describing” sequence${\{k_n\}}_{k=0}^{\mathrm{\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 http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000002sequence A000002in http://www.research.att.com/ njas/sequences/Seis.htmlthe Online Encyclopedia of Integer Sequences.