[seqfan] The Ehrenfeucht-Mycielski sequence A038219

[Neil Sloane]

Dear Seqfans,  This is a very interesting sequence.  It is by definition a
"maximally unpredictable sequence", but actually it has a simple
construction, so of course it is not unpredictable at all.
There is an open problem: show that 0's and 1's have density 1/2.   This
might be much easier to settle than the Kolakoski sequence A000002.  (One
reason I say that is that A253060 and A253061 are so regular.)

There are a bunch of related sequences:
Cf. A201881 (run lengths).
Cf. also A253059, Locations of 0's and 1's: A253060, A253061.
For first appearance of subwords see A308173.
A308174, A308175 are used in the calculation of a(n).

Remy Sigrist has kindly extended several of these sequences, and has
provided a 100000-term b-file for A038219, so there is plenty of data.

For once, the Wikipedia article (see the link in A038219) is actually
helpful.

There is presently no Maple program. The naive algorithm is O(n^3), but the
Wikipedia article mentions a much faster algorithm in the paper
Herman, Grzegorz,
and Soltys, Michael, On the Ehrenfeucht-Mycielski sequence, Journal of
Discrete Algorithms, 7 (No. 4, 2009), 500-508.

However, even a naive Maple program would be useful.