|
|
A038219
|
|
The Ehrenfeucht-Mycielski sequence (0,1-version): a maximally unpredictable sequence.
|
|
18
|
|
|
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,1
|
|
COMMENTS
|
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 most recent one. The next digit of the sequence is the opposite of the one following the previous occurrence. - Christopher Carl Heckman, Feb 10 2005
|
|
LINKS
|
|
|
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.
|
|
MAPLE
|
See Lunnon link.
|
|
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
(Perl) See Links section.
(Python)
from itertools import count, islice
def agen():
astr, preval = "010", 1
yield from [0, 1, 0]
while True:
an = 1 - preval
yield an
astr += str(an)
for l in range(len(astr)-1, 0, -1):
idx = astr.rfind(astr[-l:], 0, len(astr)-1)
if idx >= 0: preval = int(astr[idx+l]); break
|
|
CROSSREFS
|
For first appearance of subwords see A308173.
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|