On the Ehrenfeucht–Mycielski sequence

We introduce the inverted prefix tries (a variation of suffix tries) as a convenient formalism for stating and proving properties of the Ehrenfeucht–Mycielski sequence [A. Ehrenfeucht, J. Mycielski, A pseudorandom sequence—how random is it? American Mathematical Monthly 99 (1992) 373-375]. We also prove an upper bound on the position in the sequence by which all strings of a given length will have appeared; our bound is given by the Ackermann function, which, in light of experimental data, may be a gross over-estimate. Still, it is the best explicitly known upper bound at the moment. Finally, we show how to compute the next bit in the sequence in a constant number of operations.