An infinite sequence of 1's and 2's, about which very little is known (but much is suspected to be true). It describes itself, in the following sense. It begins with a 2, and alternates blocks of 1's and 2's; each digit describes the length of the next block. Thus, the first block is "22" (since the digit `2' describes the length of its own block); the second 2 means that it continues "11", so the 2 blocks following are "2" and "1".

Continuing, we have the following:

22112122122112112212112122112...

It is conjectured that the density of each digit in the sequence is 1/2, but nobody knows how to prove this. Extensive computer simulations suggest that this is indeed true, and that the number of 1's after n digits deviates from n/2 by only O(log n); this result would be much stronger than the density result. For comparison, the density of heads in a sequence of random coin flips is also 1/2, but there the deviation is (almost surely) Theta(sqrt(n)), which is much larger.

It is not even known that the 1's have a density (this would itself imply that the density is 1/2). It is also unknown if the sequence is strongly recurrent. In short, almost nothing is known...

Log in or register to write something here or to contact authors.