cp's OEIS Frontend

A038219 The Ehrenfeucht-Mycielski sequence (0,1-version): a maximally unpredictable sequence.

%I A038219 #84 Jan 29 2024 01:54:39
%S A038219 0,1,0,0,1,1,0,1,0,1,1,1,0,0,0,1,0,0,0,0,1,1,1,1,0,1,1,0,0,1,0,1,0,0,
%T A038219 1,0,0,1,1,1,0,1,0,0,0,1,1,0,0,0,0,0,1,0,1,1,0,1,1,1,1,1,0,0,1,1,0,0,
%U A038219 1,1,1,1,1,1,0,1,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,0,1
%N A038219 The Ehrenfeucht-Mycielski sequence (0,1-version): a maximally unpredictable sequence.
%C A038219 The sequence starts 0,1,0 and continues according to the following rule: find the longest suffix that has occurred at least once previously. If there is more than one previous occurrences select the most recent one. The next digit of the sequence is the opposite of the one following the previous occurrence. - _Christopher Carl Heckman_, Feb 10 2005
%H A038219 Rémy Sigrist, <a href="/A038219/b038219.txt">Table of n, a(n) for n = 1..100000</a> (first 5000 terms from Reinhard Zumkeller)
%H A038219 A. Ehrenfeucht and J. Mycielski, <a href="http://www.jstor.org/stable/2324917">A pseudorandom sequence - how random is it?</a>, Amer. Math. Monthly, 99 (1992), 373-375.
%H A038219 Grzegorz Herman and Michael Soltys, <a href="https://doi.org/10.1016/j.jda.2009.01.002">On the Ehrenfeucht-Mycielski sequence</a>, Journal of Discrete Algorithms, 7, No. 4 (2009), 500-508.
%H A038219 J. C. Kieffer and W. Szpankowski, <a href="https://hal.inria.fr/hal-01184790/">On the Ehrenfeucht-Mycielski balance conjecture</a>. Discrete Mathematics and Theoretical Computer Science (2007), 19-30.
%H A038219 Fred Lunnon, <a href="/A038219/a038219.txt">Maple Program for A038219</a> (Complexity about O(n log n) arithmetic operations)
%H A038219 Terry McConnell, <a href="https://web.archive.org/web/20181011045044/http://barnyard.syr.edu/mseq/mseq.shtml">The Ehrenfeucht-Mycielski Sequence</a>
%H A038219 Terry R. McConnell, <a href="https://arxiv.org/abs/1303.6820">DeBruijn Strings, double helices, and the Ehrenfeucht-Mycielski mechanism</a>, arXiv:1303.6820 [math.CO], 2013.
%H A038219 Rémy Sigrist, <a href="/A038219/a038219.pl.txt">Perl program for A038219</a>
%H A038219 K. Sutner, <a href="http://www.cs.cmu.edu/~sutner/papers/em-sequence.ps.gz">The Ehrenfeucht-Mycielski sequence</a>, 2001 [broken link]
%H A038219 K. Sutner, <a href="/A007061/a007061_2.pdf">The Ehrenfeucht-Mycielski sequence</a>, 2001 [Cached copy]
%H A038219 Klaus Sutner, <a href="https://doi.org/10.1007/3-540-45089-0_26">The Ehrenfeucht-Mycielski Sequence</a>, LNCS 2759 (2003) 282-293.
%H A038219 Wikipedia, <a href="https://en.wikipedia.org/wiki/Ehrenfeucht%E2%80%93Mycielski_sequence">Ehrenfeucht-Mycielski sequence</a>
%e A038219 We start with a(1)=0, a(2)=1, a(3)=0.
%e A038219 The longest suffix we have seen before is "0", when it occurred at the start, followed by 1. So a(4) = 0. We now have 0100.
%e A038219 The longest suffix we have seen before is again "0", when it occurred at a(3), followed by a(4)=0. So a(5) = 1. We now have 01001.
%e A038219 The longest suffix we have seen before is "01", when it occurred at a(1),a(2), followed by a(3)=0. So a(6) = 1. We now have 010011.
%e A038219 And so on.
%e A038219 For further illustrations of calculating these terms, see A308174 and A308175. - _N. J. A. Sloane_, May 21 2019
%p A038219 See Lunnon link.
%o A038219 (Haskell)
%o A038219 a038219 n = a038219_list !! n
%o A038219 a038219_list = 0 : f [0] where
%o A038219    f us = a' : f (us ++ [a']) where
%o A038219         a' = b $ reverse $ map (`splitAt` us) [0..length us - 1] where
%o A038219            b ((xs,ys):xyss) | vs `isSuffixOf` xs = 1 - head ys
%o A038219                             | otherwise          = b xyss
%o A038219         vs = fromJust $ find (`isInfixOf` init us) $ tails us
%o A038219 -- _Reinhard Zumkeller_, Dec 05 2011
%o A038219 (Perl) See Links section.
%o A038219 (Python)
%o A038219 from itertools import count, islice
%o A038219 def agen():
%o A038219     astr, preval = "010", 1
%o A038219     yield from [0, 1, 0]
%o A038219     while True:
%o A038219         an = 1 - preval
%o A038219         yield an
%o A038219         astr += str(an)
%o A038219         for l in range(len(astr)-1, 0, -1):
%o A038219             idx = astr.rfind(astr[-l:], 0, len(astr)-1)
%o A038219             if idx >= 0: preval = int(astr[idx+l]); break
%o A038219 print(list(islice(agen(), 105))) # _Michael S. Branicky_, Aug 03 2022
%Y A038219 Cf. A007061 (1, 2 version).
%Y A038219 Cf. A201881 (run lengths).
%Y A038219 Cf. also A253059, A253060, A253061.
%Y A038219 For first appearance of subwords see A308173.
%Y A038219 A308174, A308175 are used in the calculation of a(n).
%K A038219 nonn,nice
%O A038219 1,1
%A A038219 _N. J. A. Sloane_, _Mira Bernstein_
%E A038219 More terms from _Joshua Zucker_, Aug 11 2006
%E A038219 Offset changed by _Reinhard Zumkeller_, Dec 11 2011
%E A038219 Edited by _N. J. A. Sloane_, May 12 2019