The Kolakoski Sequence

Write down the digit 1:


This can be seen as describing itself: It might denote the length of the string of identical digits at this point in the sequence. Well, in that case, if the length of this run is only one digit, then the next digit in the sequence can’t be another 1. So write 2:

1 2

Seen in the same light, the 2 would indicate that this second run of digits has length 2. So add a second 2 to the list to fulfill that description:

1 2 2

We can continue in this way, adding 1s and 2s so that the sequence becomes a recipe for writing itself:
Animation: Wikimedia Commons

This is a fractal, a mathematical object that encodes its own representation. It was described by William Kolakoski in 1965, and before him by Rufus Oldenburger in 1939. University of Evansville mathematician Clark Kimberling is offering a reward of $200 for the solution to five problems associated with the sequence:

  1. Is there a formula for the nth term?
  2. If a string occurs in the sequence, must it occur again?
  3. If a string occurs, must its reversal also occur?
  4. If a string occurs, and all its 1s and 2s are swapped, must the new string occur?
  5. Does the limiting frequency of 1s exist, and is it 1/2?

So far, no one has found the answers.