Density of ones in the Kolakoski sequence

Prove that the self-describing Kolakoski sequence of 1s and 2s has a density of 1s, equal to 1/2.

shoal State the problem, from Formal Conjectures 24671cf · 2周前历史

40 行 · 3.3 KB 原始文件永久链接历史

1	# Density of ones in the Kolakoski sequence
2
3	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.
4
5	## Problem
6
7	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$:
8	$$1,\ 2, 2,\ 1, 1,\ 2,\ 1,\ 2, 2,\ 1,\ 2, 2,\ 1, 1,\ 2, \dots$$
9
10	Question. Does the density
11	$$\lim_{N \to \infty} \frac{1}{N} \, \#\{ n \le N : a_n = 1 \}$$
12	exist, and is it equal to $1/2$?
13
14	## Background
15
16	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).
17
18	## What is known
19
20	- 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.
21	- 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$.
22	- 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$.
23
24	## What would count as progress
25
26	- A proof that the density exists, or that it equals $1/2$.
27	- Better rigorous bounds on the upper and lower densities of 1s, for example by pushing Chvátal's method further with certified computation.
28	- Larger computations, with published code, of the discrepancy $\#\{n \le N : a_n = 1\} - N/2$, which is a natural experimental target.
29	- 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.
30
31	## References
32
33	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).
34	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.
35	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.
36	4. OEIS Foundation, [A000002: Kolakoski sequence](https://oeis.org/A000002).
37
38	## Source
39
40	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.