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$ .¹¹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(\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
Canonical name	KolakoskiSequence
Date of creation	2013-03-22 12:47:33
Last modified on	2013-03-22 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