%I M0075 #50 Jan 29 2024 01:53:38
%S 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 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 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 The Ehrenfeucht-Mycielski sequence (1,2-version): a maximally unpredictable sequence.
%C 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 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 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 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Joshua Zucker, <a href="/A007061/b007061.txt">Table of n, a(n) for n = 1..1999</a>
%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 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 Terry McConnell, <a href="https://web.archive.org/web/20181011045044/http://barnyard.syr.edu/mseq/mseq.shtml">The Ehrenfeucht-Mycielski Sequence</a>
%H K. Sutner, <a href="http://www.cs.cmu.edu/~sutner/papers/em-sequence.ps.gz">The Ehrenfeucht-Mycielski sequence</a>, 2001
%H K. Sutner, <a href="/A007061/a007061_2.pdf">The Ehrenfeucht-Mycielski sequence</a>, 2001 [Cached copy]
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Ehrenfeucht%E2%80%93Mycielski_sequence">Ehrenfeucht-Mycielski sequence</a>
%o (Haskell)
%o a007061 n = a007061_list !! (n-1)
%o a007061_list = 1 : f [1] 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 = 3 - head ys
%o | otherwise = b xyss
%o vs = fromJust $ find (`isInfixOf` init us) $ tails us
%o -- _Reinhard Zumkeller_, Dec 05 2011
%o (Python)
%o from itertools import count, islice
%o def agen():
%o astr, preval = "121", 2
%o yield from [1, 2, 1]
%o while True:
%o an = 3 - 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. A038219 (0-1 version), A079101.
%Y Cf. A201881 (run lengths).
%Y Cf. also A253059, A253060, A253061.
%K nonn
%O 1,2
%A _N. J. A. Sloane_, _Mira Bernstein_
%E More terms from _Joshua Zucker_, Aug 11 2006
%E Offset changed from 0 to 1, Aug 18 2006
|