Kolakoski sequence
A Kolakoski sequence^{} is a “selfdescribing” sequence ${\{{k}_{n}\}}_{k=0}^{\mathrm{\infty}}$ of alternating blocks of 1’s and 2’s, given by the following rules:

•
${k}_{0}=1$.^{1}^{1}Some 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(\mathrm{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(\mathrm{log}n)$ to generate the first $n$ elements.
This is http://www.research.att.com/cgibin/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 

Canonical name  KolakoskiSequence 
Date of creation  20130322 12:47:33 
Last modified on  20130322 12:47:33 
Owner  PrimeFan (13766) 
Last modified by  PrimeFan (13766) 
Numerical id  6 
Author  PrimeFan (13766) 
Entry type  Definition 
Classification  msc 11Y55 
Classification  msc 94A55 
Synonym  Kolakowski’s sequence 