|
%I #84 Jan 29 2024 01:54:39
%S 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 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 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 The Ehrenfeucht-Mycielski sequence (0,1-version): a maximally unpredictable sequence.
%C 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 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 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 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 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 Fred Lunnon, <a href="/A038219/a038219.txt">Maple Program for A038219</a> (Complexity about O(n log n) arithmetic operations)
%H Terry McConnell, <a href="https://web.archive.org/web/20181011045044/http://barnyard.syr.edu/mseq/mseq.shtml">The Ehrenfeucht-Mycielski Sequence</a>
%H 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 Rémy Sigrist, <a href="/A038219/a038219.pl.txt">Perl program for A038219</a>
%H K. Sutner, <a href="http://www.cs.cmu.edu/~sutner/papers/em-sequence.ps.gz">The Ehrenfeucht-Mycielski sequence</a>, 2001 [broken link]
%H K. Sutner, <a href="/A007061/a007061_2.pdf">The Ehrenfeucht-Mycielski sequence</a>, 2001 [Cached copy]
%H 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Ehrenfeucht%E2%80%93Mycielski_sequence">Ehrenfeucht-Mycielski sequence</a>
%e We start with a(1)=0, a(2)=1, a(3)=0.
%e 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 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 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 And so on.
%e For further illustrations of calculating these terms, see A308174 and A308175. - _N. J. A. Sloane_, May 21 2019
%p See Lunnon link.
%o (Haskell)
%o a038219 n = a038219_list !! n
%o a038219_list = 0 : f [0] where
%o f us = a' : f (us ++ [a']) where
%o a' = b $ reverse $ map (`splitAt` us) [0..length us - 1] where
%o b ((xs,ys):xyss) | vs `isSuffixOf` xs = 1 - head ys
%o | otherwise = b xyss
%o vs = fromJust $ find (`isInfixOf` init us) $ tails us
%o -- _Reinhard Zumkeller_, Dec 05 2011
%o (Perl) See Links section.
%o (Python)
%o from itertools import count, islice
%o def agen():
%o astr, preval = "010", 1
%o yield from [0, 1, 0]
%o while True:
%o an = 1 - preval
%o yield an
%o astr += str(an)
%o for l in range(len(astr)-1, 0, -1):
%o idx = astr.rfind(astr[-l:], 0, len(astr)-1)
%o if idx >= 0: preval = int(astr[idx+l]); break
%o print(list(islice(agen(), 105))) # _Michael S. Branicky_, Aug 03 2022
%Y Cf. A007061 (1, 2 version).
%Y Cf. A201881 (run lengths).
%Y Cf. also A253059, A253060, A253061.
%Y For first appearance of subwords see A308173.
%Y A308174, A308175 are used in the calculation of a(n).
%K nonn,nice
%O 1,1
%A _N. J. A. Sloane_, _Mira Bernstein_
%E More terms from _Joshua Zucker_, Aug 11 2006
%E Offset changed by _Reinhard Zumkeller_, Dec 11 2011
%E Edited by _N. J. A. Sloane_, May 12 2019
|
