login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007061 The Ehrenfeucht-Mycielski sequence (1,2-version): a maximally unpredictable sequence.
(Formerly M0075)
8

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 05:48 EDT 2024. Contains 371265 sequences. (Running on oeis4.)