A007061 -id:A007061 - cp's OEIS frontend

A201881 Run lengths in maximally unpredictable sequences A007061, A038219.

1, 1, 2, 2, 1, 1, 1, 3, 3, 1, 4, 4, 1, 2, 2, 1, 1, 1, 2, 1, 2, 3, 1, 1, 3, 2, 5, 1, 1, 2, 1, 5, 2, 2, 2, 6, 1, 1, 1, 1, 1, 2, 3, 3, 2, 1, 3, 1, 1, 1, 1, 1, 6, 2, 1, 2, 1, 1, 2, 2, 3, 1, 1, 4, 4, 1, 2, 1, 1, 2, 2, 2, 1, 3, 1, 4, 1, 1, 2, 1, 1, 1, 1, 7, 3, 2

Offset: 1

Reinhard Zumkeller, Dec 11 2011

nonn

a(2*n-1) = length of n-th block of consecutive ones in A007061, or consecutive zeros in A038219;
a(2*n) = length of n-th block of consecutive twos in A007061, or consecutive ones in A038219;
a(A201882(n)) = n and a(m) < n for m < A201882(n).

			A007061: 1, 2, 1,1, 2,2, 1, 2, 1, 2,2,2, 1,1,1, 2, 1,1,1,1, 2,2,2,2, ..
A038219: 0, 1, 0,0, 1,1, 0, 1, 0, 1,1,1, 0,0,0, 1, 0,0,0,0, 1,1,1,1, ..
A201881: 1, 1, __2, __2, 1, 1, 1, ____3, ____3, 1, ______4, ______4, ...

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

import Data.List (group)
a201881 n = a201881_list !! (n-1)
a201881_list = map length $ group a007061_list

A201882 Where the first run of length n occurs in maximally unpredictable sequences A007061, A038219.

Original entry on oeis.org

1, 3, 8, 11, 27, 36, 84, 231, 349, 535, 1267, 2916, 4114, 14349, 27045, 35059, 89723, 234443, 408129, 799350, 1926026, 2170589, 4291892, 10758318, 21141201, 57927399, 122141530, 138265841

Offset: 1

Reinhard Zumkeller, Dec 11 2011

A201881(a(n)) = n and A201881(m) < n for m < a(n).

Since every substring appears in A007061 (and A038219) this sequence is infinite. - N. J. A. Sloane, May 17 2019

Rémy Sigrist, C program

Cf. A007061, A038219.

C
```
// See Links section
```

a201882 = ((+ 1) . fromJust . (`elemIndex` a201881_list))

a(11)-a(28) from Rémy Sigrist, Jul 31 2022

A253059 Number of n-bit words missing from the first 2^n+n-1 bits of the Ehrenfeucht-Mycielski sequence (A007061 or A038219).

Original entry on oeis.org

0, 1, 2, 2, 2, 4, 7, 8, 13, 10, 62, 15, 140, 92, 300, 180, 704, 1880, 2053, 4381

Offset: 1

N. J. A. Sloane, Jan 18 2015

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

Cf. A007061, A038219.

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

Original entry on oeis.org

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

A079101 A repetition-resistant sequence.

Original entry on oeis.org

0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0

Offset: 1

Clark Kimberling, Jan 03 2003

nonn

a(n) = 0 or 1, chosen so as to maximize the number of different subsequences that are formed.
a(n+1)=1 if and only if (a(1),a(2),...,a(n),0), but not (a(1),a(2),...,a(n),1), has greater length of longest repeated segment than (a(1),a(2),...,a(n)) has.
In Feb, 2003, Alejandro Dau solved Problem 3 on the Unsolved Problems and Rewards website, thus establishing that every binary word occurs infinitely many times in this sequence.
Klaus Sutmer remarks (Jun 26 2006) that this sequence is very similar to the Ehrenfeucht-Mycielski sequence A007061. Both sequences have every finite binary word as a factor; in fact, essentially the same proof works for both sequences.
Differs from A334941 for the first time at n = 70. - Jeffrey Shallit, Dec 14 2022

			a(7)=1 because (0,1,0,0,0,1,0) has repeated segment (0,1,0) of length 3, whereas (0,1,0,0,0,1,1) has no repeated segment of length 3.

Peter J. C. Moses, Table of n, a(n) for n = 1..10000
A. Dau, Secuencia Maximizadora de Subcadenas (Interactive Java generator of repetition-resistant sequences). [Broken link]
Clark Kimberling, Unsolved Problems and Rewards.
Clark Kimberling, Problem 2289, Crux Mathematicorum 23 (1997) 501.

Cf. A079136, A079335, A079336, A079337, A079338, A007061, A334941.

A253060 Indices of 0's in Ehrenfeucht-Mycielski sequence A038219.

Original entry on oeis.org

1, 3, 4, 7, 9, 13, 14, 15, 17, 18, 19, 20, 25, 28, 29, 31, 33, 34, 36, 37, 41, 43, 44, 45, 48, 49, 50, 51, 52, 54, 57, 63, 64, 67, 68, 75, 77, 79, 82, 83, 84, 88, 89, 91, 92, 93, 95, 97, 99, 100, 101, 102, 103, 104, 107, 110, 112, 113, 116, 117, 118, 120, 125, 126, 127, 128

Offset: 1

N. J. A. Sloane, Jan 18 2015

nonn

Also positions of 1's in A007061.

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

Cf. A007061, A038219, A253061.

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.

cp's OEIS Frontend

A201881 Run lengths in maximally unpredictable sequences A007061, A038219.

Views

Author

Keywords

Comments

Examples

Links

Programs

Haskell

A201882 Where the first run of length n occurs in maximally unpredictable sequences A007061, A038219.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

Haskell

Extensions

A253059 Number of n-bit words missing from the first 2^n+n-1 bits of the Ehrenfeucht-Mycielski sequence (A007061 or A038219).

Views

Author

Keywords

Links

Crossrefs

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

A079101 A repetition-resistant sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A253060 Indices of 0's in Ehrenfeucht-Mycielski sequence A038219.

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs