A253060 -id:A253060 - cp's OEIS frontend

A038219 The Ehrenfeucht-Mycielski sequence (0,1-version): a maximally unpredictable sequence.

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

Offset: 1

N. J. A. Sloane, Mira Bernstein

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

			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

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.
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.
Fred Lunnon, Maple Program for A038219 (Complexity about O(n log n) arithmetic operations)
Terry McConnell, The Ehrenfeucht-Mycielski Sequence
Terry R. McConnell, DeBruijn Strings, double helices, and the Ehrenfeucht-Mycielski mechanism, arXiv:1303.6820 [math.CO], 2013.
Rémy Sigrist, Perl program for A038219
K. Sutner, The Ehrenfeucht-Mycielski sequence, 2001 [broken link]
K. Sutner, The Ehrenfeucht-Mycielski sequence, 2001 [Cached copy]
Klaus Sutner, The Ehrenfeucht-Mycielski Sequence, LNCS 2759 (2003) 282-293.
Wikipedia, Ehrenfeucht-Mycielski sequence

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

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

Maple
```
See Lunnon link.
```
Perl
```
See Links section.
```

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
print(list(islice(agen(), 105))) # Michael S. Branicky, Aug 03 2022

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

A007061 The Ehrenfeucht-Mycielski sequence (1,2-version): a maximally unpredictable sequence.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Mira Bernstein

nonn

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

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

Joshua Zucker, Table of n, a(n) for n = 1..1999
A. Ehrenfeucht and J. Mycielski, A pseudorandom sequence - how random is it?, Amer. Math. Monthly, 99 (1992), 373-375.
J. C. Kieffer and W. Szpankowski, On the Ehrenfeucht-Mycielski balance conjecture, Discrete Mathematics and Theoretical Computer Science, Proceedings, 2007 Conference on Analysis of Algorithms, AofA 07, (pp. 19-30).
Terry McConnell, The Ehrenfeucht-Mycielski Sequence
K. Sutner, The Ehrenfeucht-Mycielski sequence, 2001
K. Sutner, The Ehrenfeucht-Mycielski sequence, 2001 [Cached copy]
Wikipedia, Ehrenfeucht-Mycielski sequence

Cf. A038219 (0-1 version), A079101.
Cf. A201881 (run lengths).
Cf. also A253059, A253060, A253061.

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

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
print(list(islice(agen(), 105))) # Michael S. Branicky, Aug 03 2022

More terms from Joshua Zucker, Aug 11 2006

Offset changed from 0 to 1, Aug 18 2006

A253061 Indices of 1's in Ehrenfeucht-Mycielski sequence A038219.

Original entry on oeis.org

2, 5, 6, 8, 10, 11, 12, 16, 21, 22, 23, 24, 26, 27, 30, 32, 35, 38, 39, 40, 42, 46, 47, 53, 55, 56, 58, 59, 60, 61, 62, 65, 66, 69, 70, 71, 72, 73, 74, 76, 78, 80, 81, 85, 86, 87, 90, 94, 96, 98, 105, 106, 108, 109, 111, 114, 115, 119, 121, 122, 123, 124, 129, 132

Offset: 1

N. J. A. Sloane, Jan 18 2015

nonn

Also positions of 2's in A007061.

Rémy Sigrist, Table of n, a(n) for n = 1..25000

Cf. A007061, A038219, A253060.

A308173 Take the list of all binary vectors (including those beginning with 0) in lexicographic order; a(n) is the index of the first occurrence of the n-th binary vector as a subsequence of A038219.

Original entry on oeis.org

1, 2, 3, 1, 2, 5, 13, 3, 1, 4, 2, 6, 5, 10, 17, 13, 14, 3, 1, 7, 4, 9, 12, 2, 6, 8, 11, 5, 10, 21, 48, 17, 13, 18, 14, 28, 3, 19, 15, 1, 29, 7, 25, 4, 9, 20, 16, 12, 27, 2, 30, 6, 24, 8, 11, 26, 5, 23, 10, 22, 21, 58, 99, 48, 49, 17, 13, 50, 43, 18, 14, 33, 28

Offset: 1

N. J. A. Sloane, May 20 2019

nonn

Ehrenfeucht and Mycielski (1992) prove that every binary vector appears in A038219, so the sequence is well-defined.

			A038219 begins 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, ... and has offset 1. Here is the start of the list of binary vectors and the index where they first appear in the sequence:
0: 1
1: 2
00: 3
01: 1
10: 2
11: 5
000: 13
001: 3
...

Rémy Sigrist, Table of n, a(n) for n = 1..65535
A. Ehrenfeucht and J. Mycielski, A pseudorandom sequence - how random is it?, Amer. Math. Monthly, 99 (1992), 373-375.

Cf. A038219, A253060, A253061.

More terms from Rémy Sigrist, May 21 2019

cp's OEIS Frontend

A038219 The Ehrenfeucht-Mycielski sequence (0,1-version): a maximally unpredictable sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Perl

Python

Extensions

A007061 The Ehrenfeucht-Mycielski sequence (1,2-version): a maximally unpredictable sequence.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Python

Extensions

A253061 Indices of 1's in Ehrenfeucht-Mycielski sequence A038219.

Views

Author

Keywords

Comments

Links

Crossrefs

A308173 Take the list of all binary vectors (including those beginning with 0) in lexicographic order; a(n) is the index of the first occurrence of the n-th binary vector as a subsequence of A038219.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions