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 …