Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS
 Kolakoski sequence (Definition)

A “self-describing” sequence of alternating blocks of 1's and 2's, given by the following rules:

• .1
• is the length of the '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 is the number of 1's in the first elements, then it appears that . Note for comparison that for a random sequence of 1's and 2's, the number of 1's in the first elements is with high probability .

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 to generate the first elements.

#### Footnotes

....1
Some sources start the sequence at , instead. This only has the effect of shifting the sequence by one position.

"Kolakoski sequence" is owned by ariels.
(view preamble)

 View style: HTML with imagespage imagesTeX source

 Other names: Kolakowski's sequence

Cross-references: depth, generators, generate, conjecture, support, imply, density, length, sources, blocks, alternating, sequence

This is version 1 of Kolakoski sequence, born on 2002-06-16.
Object id is 3108, canonical name is KolakoskiSequence.
Accessed 3733 times total.

Classification:
 AMS MSC: 11Y55 (Number theory :: Computational number theory :: Calculation of integer sequences) 94A55 (Information and communication, circuits :: Communication, information :: Shift register sequences and sequences over finite alphabets)