Bounds for the Kolakoski Sequence
Olivier Bordellès
2 allée de la Combe
43000 Aiguilhe
France
Benoit Cloitre
19 rue Louise Michel
92300 Levallois-Perret
France
Abstract:
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