Density of ones in the Kolakoski sequence

The Kolakoski sequence $1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, \dots$ uses only the symbols 1 and 2 and describes itself: its run lengths, read in order, are the sequence again. It looks as if exactly half of its terms are 1, and computations of the first $10^{13}$ terms agree, but nobody can prove that the proportion of 1s even has a limit.

Problem

The Kolakoski sequence $(a_n)_{n \ge 1}$ is the unique sequence over $\{1, 2\}$ with $a_1 = 1$ whose $n$-th run (maximal block of equal symbols) has length $a_n$, for every $n$:

$$1,\ 2, 2,\ 1, 1,\ 2,\ 1,\ 2, 2,\ 1,\ 2, 2,\ 1, 1,\ 2, \dots$$

Question. Does the density

$$\lim_{N \to \infty} \frac{1}{N} \, \#\{ n \le N : a_n = 1 \}$$

exist, and is it equal to $1/2$?

Background

The sequence was discussed by Rufus Oldenburger in 1939 in symbolic dynamics, and posed as a puzzle by William Kolakoski in the American Mathematical Monthly in 1965. Despite the simple self-describing rule, even basic statistical questions about it, such as the frequency of each symbol, remain unanswered. The density question is recorded as unsolved in the On-Line Encyclopedia of Integer Sequences (A000002).

What is known

• Chvátal (1993) proved that the upper density of 1s is less than $0.50084$; Nilsson later improved this to $0.500080$ by the same method.
• Kupin and Rowland (2008) proved that if the limiting frequency of 1s exists, it differs from $1/2$ by at most $17/762$, and gave a semi-rigorous bound of $1/46$.
• Steinsky (2006) computed the first $3 \times 10^8$ terms; Nilsson (2012) computed the first $10^{13}$ terms with a space-efficient algorithm, finding the deviation from $1/2$ shrinking, consistent with density $1/2$.

What would count as progress

• A proof that the density exists, or that it equals $1/2$.
• Better rigorous bounds on the upper and lower densities of 1s, for example by pushing Chvátal's method further with certified computation.
• Larger computations, with published code, of the discrepancy $\#\{n \le N : a_n = 1\} - N/2$, which is a natural experimental target.
• A formal proof of the Lean statement density_one in OEIS/2.lean, where the sequence is defined from its run-length rule.

References

1. E. J. Kupin and E. S. Rowland, Bounds on the frequency of 1 in the Kolakoski word, arXiv:0809.2776 (2008).
2. B. Steinsky, A recursive formula for the Kolakoski sequence A000002, J. Integer Seq. 9 (2006), Article 06.3.7.
3. J. Nilsson, A space-efficient algorithm for calculating the digit distribution in the Kolakoski sequence, J. Integer Seq. 15 (2012), Article 12.6.7.
4. OEIS Foundation, A000002: Kolakoski sequence.

Source

Imported from Formal Conjectures OEIS/2, curated by Google DeepMind and contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.