Kolakoski sequence

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, the Kolakoski sequence (named after William Kolakoski, who discussed it in 1965[1]) is an infinite sequence of symbols {1,2} which is its own run-length encoding.[2]

The initial terms of the sequence are:

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,… (sequence A000002 in OEIS)

Each symbol occurs in a "run" of either 1 or 2 consecutive terms, and writing down the lengths of these runs gives exactly the same sequence. It is the unique sequence with this property except for the same sequence with the initial 1 deleted.[2]

Algorithm[edit]

The sequence may be generated by an algorithm that, in the ith iteration, reads the value xi that has already been output as the ith value of the sequence (or, if no such value has been output yet, sets xi = i). Then, if i is odd, it outputs xi copies of the number 1, while if i is even, it outputs xi copies of the number 2. Thus, the first few steps of the algorithm are:

  1. The first value has not yet been output, so set x1 = 1, and output 1 copy of the number 1
  2. The second value has not yet been output, so set x2 = 2, and output 2 copies of the number 2
  3. The third value x3 was output as 2 in the second step, so output 2 copies of the number 1.
  4. The fourth value x4 was output as 1 in the third step, so output 1 copy of the number 2.

etc.

Density[edit]

It seems plausible that the density of 1s is 1/2, but this conjecture remains unproved.[3] Chvátal has proved that the upper density of 1's is less than 0.50084.[4]

History[edit]

Kolakoski's self-generating sequence has attracted the interest of computer scientists as well as mathematicians. For example, Stephen Wolfram describes the Kolakoski sequence in connection with the history of cyclic tag systems.[5]

Recently Jean Berstel and Srecko Brlek discovered that the Kolakoski sequence already appeared, before Kolakoski, in a 1939 paper of Rufus Oldenburger.

See also[edit]

Notes[edit]

  1. ^ William Kolakoski, Self-Generating Runs, Problem 5304, American Mathematical Monthly, vol. 72 (1965), p. 674
  2. ^ a b Pytheas Fogg (2002) p.93
  3. ^ Integer Sequences and Arrays
  4. ^ Notes on the Kolakoski Sequence, unpublished technical report
  5. ^ A New Kind of Science, p. 895

References[edit]

External links[edit]