Kolakoski · run lengths · an open problem

Its Own Description

1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2: cut it where the digit changes and the lengths of the runs spell out the same sequence. Nobody has proved that half its terms are 1s, or that the share settles at all; proof holds it between 49.992% and 50.008%, while the counting has reached 10²⁰ terms. Run the machine that writes it, watch it stay far closer to a half than coin flips can, and watch coin flips close in on it as they are read, again and again, as their own run lengths.

A sequence that spells out its own runs

Here is how it begins:

1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2 1 1 2 1 2 2 1 1 …

Cut it wherever the digit changes: 1, 22, 11, 2, 1, 22, 1, 22, 11, 2, 11, 22. Those runs are 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2 long, which is the sequence again. Nothing else made only of 1s and 2s, starting with 1, does this. It is the second entry in the Online Encyclopedia of Integer Sequences, A000002.

Rufus Oldenburger described it first, in a 1939 paper on symbolic dynamics. William Kolakoski, who apparently did not know that paper, printed its first 41 terms as Problem 5304 in the American Mathematical Monthly in 1965 and asked for a rule that made it, a formula for its nth term, and whether it ever repeats. Necdet Üçoluk answered the next year: it does not. The rule is the machine below, and it is very short.

One tape, two heads. The read head looks at a term, and the term says how long the next run is; the digit of the runs takes turns, 1, 2, 1, 2. Because every run is at least one long, the write head always stays ahead of the read head, so the machine never needs a term it has not already written. That is the whole definition, and it settles every term forever. It does not settle the simplest question you could ask about them.

Half of them are 1s, probably

Count the 1s. In the first 10 terms there are 5. In the first 100, 49; in the first thousand, 502; in the first million, 499,986. Every count anyone has made comes out close to a half. Nobody has proved that the share is a half, and nobody has proved that it settles on any number at all. Johan Nilsson, who pushed the count to ten trillion terms in 2012, states the conjecture as a limit and then:

“Both parts of Conjecture 1 — the existence and the value — are still open.”

J. Nilsson, A space-efficient algorithm for calculating the digit distribution in the Kolakoski sequence, Journal of Integer Sequences 15 (2012), Article 12.6.7, p. 2

Nothing you can see up close forces a balance. The sequence never has three equal terms in a row, because a run of three would need a 3 to describe it; but 1, 1, 2, 1, 1, 2, … also never has three in a row, and it is two-thirds 1s. What the Kolakoski sequence has that this one lacks is the self-description, and it is easy to see what the self-description does to the count.

Read the first m terms as run lengths. The runs they write take turns, 1s then 2s, so the twos-minus-ones of what they write is an alternating sum:

(2s − 1s) written by K₁ … K_m = −K₁ + K₂ − K₃ + K₄ − … ± K_m

Wherever two equal terms sit side by side, one is added and the other taken away, and they cancel exactly. Only the terms standing alone survive, and in this sequence a term stands alone exactly where the level above it says "a run of one". So the imbalance at one scale is set by the lone terms one scale up, and their pattern is set by the scale above that, and so on up to the first few terms. Every level is the same sequence, read again. Whether that chain of cancellations must end in an exact half is the open question; what it does in practice, you can watch.

The blue walks follow every rule you can see in a short stretch of the gold one: runs of one or two, the digit changing from run to run. Only the lengths are chosen by a fair coin instead of by the sequence itself. Their spread can be worked out by hand. Take the runs in pairs, one of 1s and one of 2s: the pair adds (length of the 2s) − (length of the 1s), which is −1, 0, 0 or +1 with equal chances, so on average 0 with variance ½, and a pair covers 3 terms on average. That is a variance of exactly 1/6 per term, and over 4,002 of them, run to 10⁸ terms each, the average of (2s − 1s)² ÷ n came out at 0.169.

Kolakoski is much tighter. In its first 10⁸ terms the count of 2s minus 1s never strays further than 1,551 from even. Of the 4,002 random run sequences, the median strayed 4,707, the closest of all of them 1,577, and none stayed within 1,551. Richard Brent, who ran the count to 5 × 10¹⁷ terms with Judy-anne Osborn, found the same tightness at every scale he looked:

“From our ∆(n) computations we can conclude that |δ(n)| < n^1/2/4 for 2000 ≤ n ≤ 5 × 10¹⁷.”

R. P. Brent, Fast algorithms for the Kolakoski sequence, slides from a talk, 16 November 2016 (δ(n) is the twos-minus-ones count, ∆(n) its largest size up to n)

A random run sequence's typical distance from even is about a third of √n (√(2/π) × √(1/6) ≈ 0.33), so at any given length it is more likely than not to be outside that line. The self-description is doing something, and the next instrument tries to see what.

Read the coins as runs, then read them again

Start with fair coin flips written as 1s and 2s. Read them as run lengths and you get a random run sequence, the blue walk above. Now read that as run lengths, and read the result again. Each reading is one more level of self-description. The Kolakoski sequence is the one endless sequence that a reading leaves unchanged, and repeated readings of any start close in on it: every reading copies the agreed beginning into a longer agreed beginning. The slider asks what happens on the way.

Run in C, 1,000 coin starts per level, a million terms each: each reading squeezes the walk, and then the squeezing stops. Read once, the variance per term is 1/6, as worked out above (0.166 measured). Read twice, 0.107; three times, 0.088; four times, 0.024. From about the tenth reading on it hovers between 0.0099 and 0.0142, and Kolakoski's own value, the same average taken along its first 10¹² terms at 1,800 evenly spaced points on a log scale, is 0.0086, a little below that band. (The two are not quite the same measurement: the coin starts are many sequences at one length, Kolakoski is one sequence at many lengths.) By about the tenth reading a coin-flip start is nearly as tight as Kolakoski, and further readings make no visible difference.

Two cautions. At the high levels very few coins are left: by the 20th reading, the first million terms grow out of about 300 coin flips, and in twenty draws made with the page's engine (the verifier repeats them) at least the first 5,826 terms are already exactly Kolakoski's. Those sequences are close relatives of Kolakoski, which is the point of the experiment, but the top of the slider cannot be read as "random". And a plateau at a fixed length says nothing by itself about what happens at longer lengths. It is a picture of where the tightness comes from, not a proof of anything.

The picture that doubted

Counting is how most people first meet this question, and counting has misled before. In 2006 Bertran Steinsky published a recursive formula for the nth term and used it to compute the first 3 × 10⁸ terms. He plotted the number of runs that have begun by position n, divided by n, from 10⁸ to 3 × 10⁸. If half the terms are 1s, the runs average 1½ terms, so that ratio must tend to 2/3. He drew the curve against that line and concluded:

“If we assume that the limit of o_n/n exists and is equal to 1/2 then k_n/n must tend to 2/3. Thus, the graph in Figure 1 does not support the conjecture that o_n/n converges to 1/2.”

B. Steinsky, A recursive formula for the Kolakoski sequence A000002, Journal of Integer Sequences 9 (2006), Article 06.3.7, p. 4

The window is real: at all 201 checkpoints between 10⁸ and 3 × 10⁸ the ratio is above 2/3, and at 3 × 10⁸ it is 0.666669467. It was the window that misled, not the arithmetic. A count whose imbalance grows like the square root of n can sit on one side of the line for a very long time, and 3 × 10⁸ is only about seventeen thousand squared. Nilsson, six years later, records what happened next:

“For some time, Steinsky’s result raised doubt as to the validity of Conjecture 1; however, subsequent work by Monteil [9] suggested once again that the conjecture should hold. Monteil used a brute-force method, requiring linear time and linear space in n, to push the calculation to n = 10¹¹.”

J. Nilsson (2012), p. 2

The long view: twenty powers of ten

The count has now been taken to 10²⁰ terms. Nilsson's 2012 algorithm keeps only one short run per level of the family tree, about log n of them, and took the count to 10¹³; Ed Wynn added 10¹⁴ in 2014, and Brent, with a method that trades memory for time, added 10¹⁵ through 10¹⁹ in 2017 and 10²⁰ in 2018. The chart plots how far the share of 1s sits from a half at each power of ten.

At 10²⁰ terms, 49,999,999,999,090,850,760 are 1s: a share of 0.4999999999909085, off a half by 9.09 × 10⁻¹². The points fall with the dashed lines, as 1/√n, and mostly below both. Counts like these are strong evidence and they settle nothing: a share that drifted off a half by one part in 10²⁵ would look exactly like this. I recomputed every power of ten through 10¹², with a C transcription of Nilsson's algorithm, and every count matches the published one to the last digit (table below).

What has been proved

The proofs come from the other direction. Write the sequence above itself d times, each row the run lengths of the row below, and the columns can only take finitely many shapes; the ways one column can follow another form a finite graph, and the sequence is an endless walk through it. No walk can carry more 1s, in the long run, than the richest loop in the graph. Václav Chvátal used graphs like these in 1993 and got 0.50084. Michaël Rao, in 2012, recast them as composed transducers and pushed the bound as far as T₃₃; Nilsson printed the same number in 2014.

The bound is about the long run only: Nilsson's statement is that beyond some point the share of 1s never again exceeds 455920839/911696379, which is within 0.000080 of a half, and Rao points out a symmetry of the transducers that makes the same number bound the 2s. So the share of 1s is held between about 49.992% and 50.008%, whether or not it settles. Rao also says why the ladder stops at 33: the method needs a table of 2ⁿ sixty-four-bit numbers, and each rung doubles it.

“Monter au dessus de T³³ devient difficile, car les algorithmes efficaces et parallélisables pour calculer le cycle moyen maximum (algorithme d’Howard et variantes) manipulent un vecteur de valeurs (ici, des entiers 64 bits) de la taille le nombre de sommet du transducteur, c’est à dire 2ⁿ.”

M. Rao, Trucs et bidules sur la séquence de Kolakoski, 2012 (last modified 1 October 2012). In English: going beyond T₃₃ becomes hard, because the efficient parallel algorithms for the maximum mean cycle work on a vector of 64-bit values as long as the transducer has vertices, which is 2ⁿ.

Twenty powers of ten counted; a band of 0.00016 proved. The same gap holds for the sequence's other open questions, as Brent's 2016 slides list them from Michel Dekking: whether every block of terms that appears once appears infinitely often, whether its reversal appears, whether its 1s-and-2s swap appears. For a sequence defined in one sentence, almost nothing about its long-run behaviour is known.

What I recomputed, against what was published

Published counts are Nilsson's 2012 Table 1 (through 10¹³) and OEIS A195206; Brent's columns are from his 2016 slides, which give δ(n) at 10³, 10⁶, 10⁹ and 10¹², and ∆(n)/√n at those and at every power of ten from 10¹⁰ up (and at larger n than this page reached). A dash means the source does not give that figure.

Sources

1. N. J. A. Sloane (ed.), A000002, Kolakoski sequence, and A195206, number of 1s in the first 10ⁿ entries, the On-Line Encyclopedia of Integer Sequences (fetched 2026-10-03).
2. J. Nilsson, A space-efficient algorithm for calculating the digit distribution in the Kolakoski sequence, Journal of Integer Sequences 15 (2012), Article 12.6.7.
3. J. Nilsson, Letter frequencies in the Kolakoski sequence, Acta Physica Polonica A 126 (2014), 549–552.
4. B. Steinsky, A recursive formula for the Kolakoski sequence A000002, Journal of Integer Sequences 9 (2006), Article 06.3.7.
5. R. P. Brent, Fast algorithms for the Kolakoski sequence, slides from a talk, 16 November 2016 (joint work with J. Osborn).
6. M. Rao, Trucs et bidules sur la séquence de Kolakoski, 2012, in French.
7. V. Chvátal, Notes on the Kolakoski sequence, DIMACS Technical Report 93-84, 1993. I could not reach the report itself; its bound, 0.50084, is as given by Wikipedia, and Rao's page reprints Chvátal's table of graph bounds, whose last row is 10456/20877 = 0.500838.
8. R. Oldenburger, Exponent trajectories in symbolic dynamics, Transactions of the American Mathematical Society 46 (1939), 453–466; W. Kolakoski, Problem 5304, American Mathematical Monthly 72 (1965), 674, with N. Üçoluk's solution in 73 (1966), 681–682. (Cited as Nilsson and Brent describe them.)