login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

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
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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.

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).

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

REFERENCES

A. Ehrenfeucht and J. Mycielski, A pseudorandom sequence - how random is it?, Amer. Math. Monthly, 99 (1992), 373-375.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Joshua Zucker, Table of n, a(n) for n = 1..1999

Terry McConnell, The Ehrenfeucht-Mycielski Sequence

K. Sutner, The Ehrenfeucht-Mycielski sequence, 2001

K. Sutner, The Ehrenfeucht-Mycielski sequence, 2001 [Cached copy]

PROG

(Haskell)

a007061 n = a007061_list !! (n-1)

a007061_list = 1 : f [1] where

   f us = a' : f (us ++ [a']) where

     a' = b $ reverse $ map (`splitAt` us) [0..length us - 1] where

        b ((xs, ys):xyss) | vs `isSuffixOf` xs = 3 - head ys

                         | otherwise          = b xyss

     vs = fromJust $ find (`isInfixOf` init us) $ tails us

-- Reinhard Zumkeller, Dec 05 2011

CROSSREFS

Cf. A038219 (0-1 version), A079101.

Cf. A201881 (run lengths).

Cf. also A253059, A253060, A253061.

Sequence in context: A206719 A240086 A093914 * A001817 A214973 A091954

Adjacent sequences:  A007058 A007059 A007060 * A007062 A007063 A007064

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Mira Bernstein

EXTENSIONS

More terms from Joshua Zucker, Aug 11 2006

Offset changed from 0 to 1, Aug 18 2006

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified August 18 16:01 EDT 2017. Contains 290727 sequences.