The Kolakoski sequence is the integer sequence consisting of 1s and 2s in which the th term
gives the length of the
th run. It begins 1, 2, 2, 1, 1, 2,
1, 2, 2, 1, 2, 2, 1, 1, 2, ... (OEIS A000002).
A related variant has its th term equal to the length of its
st run. To construct this variant,
start with the single digit 1 (the first "block").
Here, the single 1 means that block of length one follows the first block. Therefore,
require that the next block is 2, giving the sequence
12.
Now, the 2 means that the next (third) block will have length two, so append 11 and obtain the sequence 1211. We have added two 1s, so the
fourth and fifth blocks have length one each, giving 12112 and then 121121. As a
result of adding 21, we obtain 121121221. As a result of adding 221, we obtain 12112122122112,
and so on, giving the sequence 1, 2, 1, 1, 2, 1, 2,
2, 1, 2, 2, 1, 1, 2, ... (OEIS A006928). The
sequence after successive iterations
is given by 1, 12, 1211, 121121, 121121221, ..., and the lengths of this sequence
after steps , 2, ... are given by 1, 2, 4, 6, 9, 14, 22, ... (OEIS
A042942).
The Kolakoski sequence itself is obtained by starting with 1, 2, 2 and undertaking the above procedure beginning with the last 2. Deleting the third term, which is
2, from this sequence gives OEIS A006928. A
different growth process replaces a finite list of run
lengths with alternating runs of 1s and 2s, starting with
1s. Iterating this process from the one-term list
2 produces 2, 11, 12, 122, 12211, ..., whose lengths are 1, 2, 2, 3, 5, 7, 10, 15,
... (OEIS A001083). For , term
of OEIS A042942 is one
less than term
of OEIS A001083.
A recurrence plot of the Kolakoski sequence is illustrated above.
The constant obtained from OEIS A000002 by deleting its initial 1, taking and
, and interpreting the result
as a binary fraction
(OEIS A118270) is sometimes known as the Kolakoski constant (Plouffe).
The question of whether the number of 1s is "asymptotically" equal to the number of 2s is unsettled, although the above plot (which shows the fraction of 1s as a function of number of digits) is certainly consistent with 1 and 2 being equidistributed.