ExplorationsA sequence of 1s and 2s that lists its own run lengths

The Kolakoski Sequence

Conjecturedself-referencerun-length encodingdensitycurious

Write a sequence of 1s and 2s, split it into runs of equal terms, and count each run: 1, 2, 2, 1, 1, 2 splits into 1, then 22, then 11, then 2, so its run lengths are 1, 2, 2, 1. The Kolakoski sequence is the one whose list of run lengths is the sequence itself, beginning 1, 2, 2, 1, 1, 2, 1, 2, 2, 1. Whether 1s and 2s end up equally common is unproved.

Current view: Runs and their lengths

Watch each term set the length of a later run.

Runs and their lengths · letters 1 and 222 of 22 runs

Runs

The numbers under the brackets: 1221121221221121122121
The sequence itself: 1221121221221121122121

They are the same digits, which is the entire definition rather than a coincidence of these 22 runs.

The same data as a table

Each drawn run, its letter, the terms it occupies, and the term of the sequence that fixed its length.
Run	Letter	Length	Terms	Term that set it
0	1	1	0	term 0 = 1
1	2	2	1 to 2	term 1 = 2
2	1	2	3 to 4	term 2 = 2
3	2	1	5	term 3 = 1
4	1	1	6	term 4 = 1
5	2	2	7 to 8	term 5 = 2
6	1	1	9	term 6 = 1
7	2	2	10 to 11	term 7 = 2
8	1	2	12 to 13	term 8 = 2
9	2	1	14	term 9 = 1
10	1	2	15 to 16	term 10 = 2
11	2	2	17 to 18	term 11 = 2
12	1	1	19	term 12 = 1
13	2	1	20	term 13 = 1
14	1	2	21 to 22	term 14 = 2
15	2	1	23	term 15 = 1
16	1	1	24	term 16 = 1
17	2	2	25 to 26	term 17 = 2
18	1	2	27 to 28	term 18 = 2
19	2	1	29	term 19 = 1
20	1	2	30 to 31	term 20 = 2
21	2	1	32	term 21 = 1

term: one place in the sequence, drawn as a tile
run: a block of equal terms with a bracket under it
run length: how many terms that block contains, printed under its bracket
the pen: the term whose value fixed the length of the run being written

The top row is the sequence, one tile per term. A bracket under a block of equal tiles marks one run, and the number under the bracket is that run’s length. The outlined tile is the term whose value produced the run being written, so the row of bracket numbers is the top row read again.

22 of 22 runs drawn, covering the first 33 terms. Every one of their lengths is the term at the matching position.

Terms generated: 1,000,000

How this page is laid out

Make a prediction

Change the assumption

What this assumes: Because the sequence lists its own run lengths, about half of its terms are the smaller letter.
What breaks it: The letters are 1 and 3. The sequence still lists its own run lengths exactly, but only 397,215 of its first 1,000,000 terms are 1s, a proportion near 0.397.

Where it holds

The letters 1 and 2, where the proportion of 1s in the first million terms is very close to a half and every computation published agrees. A limit of one half is conjectured, not proved.

The two letters

Runs alternate between the two letters and the smaller one starts the sequence. Only 1 and 2 give the classical Kolakoski sequence, and only that pair has a proved interval around its proportion.

Step by step

Run, Step and Reset are under the figure. Run writes the 22 bracketed runs out one at a time, marking the term that fixed each length; Reset puts them all back. Speed sets how fast.

Speed

How much to generate

The reading figure draws the opening runs whatever this is. The proportion is counted across the whole generated prefix, and a longer prefix is a longer count rather than a stronger kind of statement.

Cases worth seeing

Try this

The sequence starts 1, 2. What forces the third term to be 2 as well?

1/2

What is going on

Each explanation begins with a worked example and follows the same operation through intuition, formal statements and proofs. Later sections distinguish what is established from questions that remain open, so you can follow the level of detail useful to you.

Worked by handStarting from 122, each line reads the digits in hand as run lengths and writes those runs out, alternating 1s and 2s.

1221 22 1112211Three terms in hand, so three runs: one 1, then two 2s, then two 1s.
122111 22 11 2 11221121The two new terms, 1 and 1, add a run of one 2 and a run of one 1.
12211211 22 11 2 1 22 11221121221Seven terms give seven runs, and the first five runs are the ones already written.
12211212211 22 11 2 1 22 1 22 11 2122112122122112Ten terms give fifteen, and every line so far is the opening of the next.

The laboratory draws the same thing with brackets: a block of equal tiles is one run, and the number under its bracket is that run's length. Reading those numbers left to right gives the row of tiles again.

Every line begins with the line above it. Nothing is ever revised, so the four lines are not four guesses at the sequence: they are four lengths of one sequence that the rule has already decided.

What you are seeing

A row of tiles and the lengths of its own blocks

The top row is a sequence of 1s and 2s. Wherever equal tiles sit next to each other they form a block, called a run, and each run is marked with a bracket. Under every bracket is a single number: how many tiles that run contains.

Read those numbers left to right and you get 1, 2, 2, 1, 1, 2, 1, and so on. That is the top row again. The sequence is the list of its own run lengths, which is the only thing being asked of it.

Why it starts to make sense

Each term is an instruction for a later run

Because the two letters alternate from run to run, the only thing left to decide about run number $k$ is how long it is, and the rule says that is the $k$ -th term. So term 0 describes run 0, term 1 describes run 1, and a term written early becomes an instruction obeyed later.

Follow the outlined tile in the reading view and you are watching that instruction being carried out. It is always behind the writing, never level with it or ahead of it, which is why the sequence can be built from left to right with nothing to guess and nothing to go back and fix.

The key idea

One rule fixes every term, and still hides the simplest count

Nothing here is random and nothing is chosen. Give the two letters and the rule forces the whole sequence, term by term, forever. A reader can generate as much of it as they have patience for.

That makes what happens next unusual. Ask how often a 1 occurs and the answer stops being computable in the same sense: you can count the 1s in any prefix, and the counts do settle near a half, but no argument is known that says they must. The rule that determines everything does not obviously determine that.

Formal statement

The sequence, and the question about it

Fix $a < b$ and let $s$ be a sequence over ${a, b}$ with $s_{0} = a$ . Write $s$ as maximal runs $R_{0} R_{1} R_{2} \dots$ , so consecutive runs use different letters and run $R_{k}$ is made of the letter $a$ when $k$ is even and $b$ when $k$ is odd. Say $s$ is self-describing when

∣ R_{k} ∣ = s_{k} for every k \geq 0.

For $a = 1, b = 2$ this is the Kolakoski sequence, entry A000002 in the encyclopedia of integer sequences. Writing $d_{n}$ for the proportion of 1s among $s_{0}, \dots, s_{n - 1}$ , the conjecture is that $d_{n} \to 1/2$ . Chvátal proved that every limit point of $d_{n}$ lies in $[0.499162, 0.500838]$ ; that the sequence $d_{n}$ converges at all is not known.

Proof

What the construction does establish

Exactly one self-describing sequence over ${a, b}$ starts with $a$ , and the construction here writes it. Suppose runs $R_{0}, \dots, R_{k - 1}$ have been written. Their letters were forced by alternation and their lengths by the terms $s_{0}, \dots, s_{k - 1}$ , so the opening $∣ R_{0} ∣ + \dots + ∣ R_{k - 1} ∣$ terms are determined, and no other self-describing sequence over these letters can differ from them. Run $R_{k}$ must then use its own forced letter and have length $s_{k}$ , so it too is determined, provided $s_{k}$ has already been written.

It has. Each run contributes at least one term, so after $k$ runs at least $k$ terms exist, and the index $k$ is at most the number of terms written. When it is strictly less, $s_{k}$ is already on the page. When the two are equal, $s_{k}$ is the first term of $R_{k}$ itself, which is the letter that run is made of, and that letter is known before the run is written. Induction completes the argument.

This proves that the picture on screen is the sequence and that it is the only one. It proves nothing about the proportion of 1s, which is the next layer's business.

Limits and further questions

A settled-looking number that nobody has pinned down

After a million terms, 499,986 of them are 1s. That is a count, not a limit, and the difference is the whole of the open problem. The density view draws Chvátal's interval around one half so the gap between the two kinds of statement is visible: the band is proved, the centre of it is not.

The clearest evidence that self-description alone is not enough is one control away. Change the letters to 1 and 3 and the sequence still lists its own run lengths exactly, yet 1s make up 0.397215 of its first million terms rather than anything near a half. Any proof about the classical case has to use something more than the defining property, because the defining property is shared.

Two further questions travel with this one. It is not known whether the sequence is what is called recurrent, meaning that every block occurring in it occurs infinitely often, and no formula is known that gives the $n$ -th term without generating the ones before it. The Thue-Morse sequence, linked below, has exactly such a formula, which is a fair measure of how much less is understood here.

What is actually established

Every statement on this page, with its status, its exact scope, and the date that status was last checked.

Exhaustively checked

In the first million terms over the letters 1 and 2, every complete run has exactly the length the sequence records at the matching position.

Scope: The first 1,000,000 terms only. The final run of that prefix is excluded because a prefix can cut a run short, so 666,672 complete runs were compared.
Why: The prefix is generated, split into runs, and each run length is compared with the term at the same index. Nothing about terms beyond a million follows from this.
Computation (exact): First 1,000,000 terms over the alphabet {1, 2}; 666,672 complete runs compared with the terms at the same indices, in exact integer arithmetic. Algorithm kolakoski-forward-pointer-1.
Status checked: 14 September 2026
Sources: A000002: the Kolakoski sequence citation unresolved

Proved

For each pair of letters, exactly one sequence over those letters begins with the smaller one and has its own terms as its run lengths, and the construction on this page produces it.

Scope: The existence and uniqueness of that sequence, for any two whole numbers a and b with 1 <= a < b <= 9. This says nothing about how often either letter occurs.
Why: Runs of a two-letter sequence alternate, so run k is made of the letter fixed by whether k is even or odd, and the definition fixes its length as the k-th term. Reading the terms in order therefore forces every run in turn, and the induction in the proof layer shows the pointer always has the term it needs before it needs it.
Status checked: 14 September 2026
Sources: Problem 5304: Self generating runs citation unresolved

Proved

For the letters 1 and 2, every limit point of the proportion of 1s in the first n terms lies between 0.499162 and 0.500838.

Scope: Chvátal’s published bounds, quoted here and drawn on the density view. They are not recomputed in this browser, and they concern the limit points rather than any single prefix.
Why: The proof is a computer-assisted argument in the cited technical report. This page draws the interval and checks that its own measured proportions fall inside it, which is a consistency check rather than a verification of the theorem.
Status checked: 14 September 2026
Sources: Notes on the Kolakoski sequence citation unresolved

Conjectured

For the letters 1 and 2, the proportion of 1s in the first n terms tends to one half.

Scope: The infinite sequence over {1, 2}. Even the existence of the limit is unproved; the proved statement is the interval above.
Why: Widely believed and supported by every computation anyone has published, including the one on this page. Neither the limit nor its value has been established.
Status checked: 14 September 2026
Sources: Notes on the Kolakoski sequence citation unresolved; A000002: the Kolakoski sequence citation unresolved

Observed in this run

Among the first 1,000,000 terms over the letters 1 and 2, exactly 499,986 are 1s, a proportion of 0.499986.

Scope: This configuration only: the alphabet {1, 2} and one million terms. A different length gives a different count.
Why: Counted from the generated prefix. It sits inside the proved interval, which is what the density view draws, and it is evidence about a million terms and nothing more.
Status checked: 14 September 2026