PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
create new user
forget your password?
Main Menu
Kolakoski sequence (Definition)

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$.1
  • $ 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 sequence A000002 in the Online Encyclopedia of Integer Sequences.


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

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

View style:

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.

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

Pending Errata and Addenda
Style: Expand: Order:
forum policy
Zeroes versus 2 by XJamRastafire on 2002-06-19 10:19:48
Simple question. (Perhaps too dumb.) Is there any difference if we change in Kolakoski sequence 2's with zeroes (0)? I guess there are no differences in densities of 1 and 2 (0). They would probably be in terms as sums and such are.

Is a term strongly recurrent sequence already defined somewhere within PlanetMath. If not, it would be fine to explain it a bit.
[ reply | up ]

rate | post | correct | update request | add derivation | add example | add (any)