Kolakoski sequence

A Kolakoski sequenceMathworldPlanetmath is a “self-describing” sequence {kn}k=0 of alternating blocks of 1’s and 2’s, given by the following rules:

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

  • kn 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 on is the number of 1’s in the first n elements, then it appears that on=0.5n+O(logn). 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(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(logn) 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