The Ehrenfeucht-Mycielski Sequence
This sequence of binary digits was introduced by
A. Ehrenfeucht
and
J. Mycielski
in A psuedo-random sequence: how random is it?, Amer. Math.
Monthly, 99 (1992), 373-375. The sequence starts 010
and continues according to the following rule: find the longest sequence at
the end that has occurred at least once previously. If there are more than
one previous occurrences select the last one. The next digit of the sequence
is the opposite of the one following the previous occurrence.
Thus, the
sequence begins
010011010111000100001111011...
An unpublished manuscript I have written about this and related sequences
entitled Laws of large numbers for some non-repetitive sequences
is available in either postscript or
tex source form.
Files containing varying numbers of terms of the sequence are available below
for experimentation. (The files, after any necessary uncompression, contain
only binary digits and newlines every 80 characters):