# 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](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/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](https://arxiv.org/abs/0809.2776), arXiv:0809.2776 (2008).
2. B. Steinsky, [A recursive formula for the Kolakoski sequence A000002](https://cs.uwaterloo.ca/journals/JIS/VOL9/Steinsky/steinsky5.html), 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](https://cs.uwaterloo.ca/journals/JIS/VOL15/Nilsson/nilsson5.html), J. Integer Seq. **15** (2012), Article 12.6.7.
4. OEIS Foundation, [A000002: Kolakoski sequence](https://oeis.org/A000002).

## Source

Imported from [Formal Conjectures OEIS/2](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/OEIS/2.lean), 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.