Journal of Integer Sequences, Vol. 14 (2011), Article 11.2.1

Bounds for the Kolakoski Sequence

Olivier Bordellès
2 allée de la Combe
43000 Aiguilhe

Benoit Cloitre
19 rue Louise Michel
92300 Levallois-Perret


The Kolakoski sequence (Kn) is perhaps one of the most famous examples of self-describing sequences for which some problems are still open. In particular, one does not know yet whether the density of 1's in this sequence is equal to 1/2. This work, which does not answer this question, provides explicit bounds for the main sequences related to (Kn). The proofs rest on a new identity involving the partial sums of (Kn) and on Dirichlet's pigeonhole principle which allows us to improve notably on the error-term.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequence A000002.)

Received November 7 2010; revised version received January 28 2010. Published in Journal of Integer Sequences, February 9 2010.

Return to Journal of Integer Sequences home page