cp's OEIS Frontend

A007061 The Ehrenfeucht-Mycielski sequence (1,2-version): a maximally unpredictable sequence.

%I A007061 M0075 #50 Jan 29 2024 01:53:38
%S A007061 1,2,1,1,2,2,1,2,1,2,2,2,1,1,1,2,1,1,1,1,2,2,2,2,1,2,2,1,1,2,1,2,1,1,
%T A007061 2,1,1,2,2,2,1,2,1,1,1,2,2,1,1,1,1,1,2,1,2,2,1,2,2,2,2,2,1,1,2,2,1,1,
%U A007061 2,2,2,2,2,2,1,2,1,2,1,2,2,1,1,1,2,2,2,1,1,2,1,1,1,2,1,2,1,2,1,1,1,1,1,1,2
%N A007061 The Ehrenfeucht-Mycielski sequence (1,2-version): a maximally unpredictable sequence.
%C A007061 Klaus Sutner remarks (Jun 26 2006) that this sequence is very similar to the Kimberling sequence A079101. Both sequences have every finite binary word as a factor; in fact, essentially the same proof works for both sequences.
%C A007061 Sutner continues: All words of length k seem to appear in the first 2^{k+2} bits. This is true for the first billion bits of the sequence, but no proof is known. The main open problem is whether the limiting density of 0's is 1/2. It seems to require a large amount of effort just to show that it is bounded away from 0, never mind some of the more exotic properties of the sequence (see the Sutner reference).
%C A007061 Start with a single bit 0. If the first n bits U(n) = a(1)a(2)...a(n) have already been chosen, let v be the longest suffix of U(n) that already appears in U(n-1). Find the last occurrence of v in U(n-1) and let b the bit that occurs immediately after. Then a(n+1) is the complement of b. (The entry gives the bits as 1's and 2s instead of 0's and 1's - compare A038219) - _Joshua Zucker_, Aug 11 2006
%D A007061 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007061 Joshua Zucker, <a href="/A007061/b007061.txt">Table of n, a(n) for n = 1..1999</a>
%H A007061 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 A007061 J. C. Kieffer and W. Szpankowski, <a href="https://doi.org/10.46298/dmtcs.3542">On the Ehrenfeucht-Mycielski balance conjecture</a>, Discrete Mathematics and Theoretical Computer Science, Proceedings, 2007 Conference on Analysis of Algorithms, AofA 07, (pp. 19-30).
%H A007061 Terry McConnell, <a href="https://web.archive.org/web/20181011045044/http://barnyard.syr.edu/mseq/mseq.shtml">The Ehrenfeucht-Mycielski Sequence</a>
%H A007061 K. Sutner, <a href="http://www.cs.cmu.edu/~sutner/papers/em-sequence.ps.gz">The Ehrenfeucht-Mycielski sequence</a>, 2001
%H A007061 K. Sutner, <a href="/A007061/a007061_2.pdf">The Ehrenfeucht-Mycielski sequence</a>, 2001 [Cached copy]
%H A007061 Wikipedia, <a href="https://en.wikipedia.org/wiki/Ehrenfeucht%E2%80%93Mycielski_sequence">Ehrenfeucht-Mycielski sequence</a>
%o A007061 (Haskell)
%o A007061 a007061 n = a007061_list !! (n-1)
%o A007061 a007061_list = 1 : f [1] where
%o A007061    f us = a' : f (us ++ [a']) where
%o A007061      a' = b $ reverse $ map (`splitAt` us) [0..length us - 1] where
%o A007061         b ((xs,ys):xyss) | vs `isSuffixOf` xs = 3 - head ys
%o A007061                          | otherwise          = b xyss
%o A007061      vs = fromJust $ find (`isInfixOf` init us) $ tails us
%o A007061 -- _Reinhard Zumkeller_, Dec 05 2011
%o A007061 (Python)
%o A007061 from itertools import count, islice
%o A007061 def agen():
%o A007061     astr, preval = "121", 2
%o A007061     yield from [1, 2, 1]
%o A007061     while True:
%o A007061         an = 3 - preval
%o A007061         yield an
%o A007061         astr += str(an)
%o A007061         for l in range(len(astr)-1, 0, -1):
%o A007061             idx = astr.rfind(astr[-l:], 0, len(astr)-1)
%o A007061             if idx >= 0: preval = int(astr[idx+l]); break
%o A007061 print(list(islice(agen(), 105))) # _Michael S. Branicky_, Aug 03 2022
%Y A007061 Cf. A038219 (0-1 version), A079101.
%Y A007061 Cf. A201881 (run lengths).
%Y A007061 Cf. also A253059, A253060, A253061.
%K A007061 nonn
%O A007061 1,2
%A A007061 _N. J. A. Sloane_, _Mira Bernstein_
%E A007061 More terms from _Joshua Zucker_, Aug 11 2006
%E A007061 Offset changed from 0 to 1, Aug 18 2006