DIMACS TR: 93-84

Notes on the Kolakoski Sequence

Author: Vasek Chvatal


The Kolakoski sequence, 12211212212211211221211212211211212212211212212112..., is the unique countable 1-2 sequence a_1a_2a_3... with a_1=1, whose j-th block has length a_j; Keane asked whether the density of 1's (and therefore also the density of 2's) in this sequence is 0.5. The purpose of this note is twofold: (i) to report computations proving that the upper density of 1's as well as the upper density of 2' in the Kolakoski sequence is less than 0.501, and (ii) to speculate about possible ways of answering Keane's question in the affirmative.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-84.ps
DIMACS Home Page