

A038219


A maximally unpredictable sequence.


8



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 sequence at the end that has occurred at least once previously. If there are more than one previous occurrences select the last one. The next digit of the sequence is the opposite of the one following the previous occurrence.


REFERENCES

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


LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..5000
K. Sutner, The EhrenfeuchtMycielski sequence
Terry McConnell, The EhrenfeuchtMycielski Sequence


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


CROSSREFS

Cf. A007061 (1, 2 version).
Cf. A201881 (run lengths).
Sequence in context: A189572 A244735 A245938 * A172486 A189668 A215530
Adjacent sequences: A038216 A038217 A038218 * A038220 A038221 A038222


KEYWORD

nonn,nice


AUTHOR

N. J. A. Sloane, Mira Bernstein


EXTENSIONS

More terms from Joshua Zucker, Aug 11 2006
Offset changed by Reinhard Zumkeller, Dec 11 2011


STATUS

approved



