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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A038219 The Ehrenfeucht-Mycielski sequence (0,1-version): a maximally unpredictable sequence. 16
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1

COMMENTS

Comment from Christopher Carl Heckman, Feb 10 2005: 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 the most recent one. The next digit of the sequence is the opposite of the one following the previous occurrence.

REFERENCES

Grzegorz Herman and Michael Soltys, On the Ehrenfeucht-Mycielski sequence, Journal of Discrete Algorithms, 7, No. 4 (2009), 500-508.

J. C. Kieffer and W. Szpankowski, On the Ehrenfeucht-Mycielski balance conjecture. Discrete Mathematics and Theoretical Computer Science (2007), 19-30.

LINKS

Rémy Sigrist, Table of n, a(n) for n = 1..100000 (first 5000 terms from Reinhard Zumkeller)

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

Terry McConnell, The Ehrenfeucht-Mycielski Sequence

Rémy Sigrist, Perl program for A038219

K. Sutner, The Ehrenfeucht-Mycielski sequence, 2001

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

Wikipedia, Ehrenfeucht-Mycielski sequence

EXAMPLE

We start with a(1)=0, a(2)=1, a(3)=0.

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.

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.

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.

And so on.

For further illustrations of calculating these terms, see A308174 and A308175. - N. J. A. Sloane, May 21 2019

PROG

(Haskell)

a038219 n = a038219_list !! n

a038219_list = 0 : f [0] 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 = 1 - head ys

                            | otherwise          = b xyss

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

-- Reinhard Zumkeller, Dec 05 2011

(Perl) See Links section.

CROSSREFS

Cf. A007061 (1, 2 version).

Cf. A201881 (run lengths).

Cf. also A253059, A253060, A253061.

For first appearance of subwords see A308173.

A308174, A308175 are used in the calculation of a(n).

Sequence in context: A288633 A284775 A156259 * A138710 A255817 A179829

Adjacent sequences:  A038216 A038217 A038218 * A038220 A038221 A038222

KEYWORD

nonn,nice,changed

AUTHOR

N. J. A. Sloane, Mira Bernstein

EXTENSIONS

More terms from Joshua Zucker, Aug 11 2006

Offset changed by Reinhard Zumkeller, Dec 11 2011

Edited by N. J. A. Sloane, May 12 2019

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 26 03:48 EDT 2019. Contains 323579 sequences. (Running on oeis4.)