Kolakoski sequence

[2] It is named after the recreational mathematician William Kolakoski (1944–97) who described it in 1965,[3] but it was previously discussed by Rufus Oldenburger in 1939.

If K stands for "the Kolakoski sequence", description #1 logically implies description #2 (and vice versa): Accordingly, one can say that each term of the Kolakoski sequence generates a run of one or two future terms.

Each number in the sequence is the length of the next run to be generated, and the element to be generated alternates between 1 and 2: As can be seen, the length of the sequence at each stage is equal to the sum of terms in the previous stage.

[9] The Kolakoski sequence can also be described as the result of a simple cyclic tag system.

Thus, the first few steps of the algorithm are: This algorithm takes linear time, but because it needs to refer back to earlier positions in the sequence it needs to store the whole sequence, taking linear space.

Visualisation of the 3rd to 50th terms of the Kolakoski sequence as a spiral. The terms start at the dot at the middle of the spiral. In the following revolution, each arc is repeated if the term is 1, or divided into two equal halves if it is 2. The first two terms cannot be shown as they are self-referential. In the SVG image , hover over an arc or label to highlight it and show its statistics.
the Kolakoski sequence describes its own run length
An animated gif illustrating how later terms of the Kolakoski sequence are generated by earlier terms.
An animated gif illustrating how later terms of the Kolakoski sequence are generated by earlier terms.