|
|
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
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
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
(Python)
from itertools import count, islice
def agen():
astr, preval = "121", 2
yield from [1, 2, 1]
while True:
an = 3 - 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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Offset changed from 0 to 1, Aug 18 2006
|
|
STATUS
|
approved
|
|
|
|