# 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$.11Some sources start the sequence at $k_{0}=2$, instead. This only has the effect of shifting the sequence by one position.

• $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 A000002 in http://www.research.att.com/ njas/sequences/Seis.htmlthe Online Encyclopedia of Integer Sequences.

Title Kolakoski sequence KolakoskiSequence 2013-03-22 12:47:33 2013-03-22 12:47:33 PrimeFan (13766) PrimeFan (13766) 6 PrimeFan (13766) Definition msc 11Y55 msc 94A55 Kolakowski’s sequence