Bounds for the Kolakoski Sequence
2 allée de la Combe
19 rue Louise Michel
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,
(Concerned with sequence
Received November 7 2010;
revised version received January 28 2010.
Published in Journal of Integer Sequences, February 9 2010.
Journal of Integer Sequences home page