A038219 -id:A038219 - cp's OEIS frontend

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

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.

A201881 Run lengths in maximally unpredictable sequences A007061, A038219.

Original entry on oeis.org

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

A308174 Let EM denote the Ehrenfeucht-Mycielski sequence A038219, and let P(n) = [EM(1),...,EM(n)]. To compute EM(n+1) for n>=3, we find the longest suffix S (say) of P(n) which has previously appeared in P(n). Suppose the most recent appearance of S began at index n-t(n). Then a(n) = length of S, while t(n) is given in A308175.

Original entry on oeis.org

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

Offset: 3

N. J. A. Sloane, May 21 2019, corrected and extended May 21 2019

nonn

Then EM(n+1) is the complement of the bit following the most recent appearance of S.

			Tableau showing calculation of terms 3 through 13
1   2   3   4   5   6   7   8   9  10  11  12  13  n
0   1   0   0   1   1   0   1   0   1   1   1   0  A038219(n)
-   -   0   0  01   1  10  01 010 101 011  11 110  S
-   -   1   1   2   1   2   2   3   3   3   2   3  s = A308174(n)
-   -   1   3   1   5   2   4   1   6   4  10   5  previous
-   -   2   1   4   1   5   4   8   4   7   2   8  t = A308175(n)
"Previous" = index of start of most recent previous occurrence of S; s = |S|; t = n - "previous" = A308175(n)

Rémy Sigrist, Table of n, a(n) for n = 3..50000
Rémy Sigrist, Perl program for A308174

Cf. A038219, A308175.

Perl
```
See Links section.
```

More terms from Rémy Sigrist, May 21 2019

A308175 Let EM denote the Ehrenfeucht-Mycielski sequence A038219, and let P(n) = [EM(1),...,EM(n)]. To compute EM(n+1) for n>=3, we find the longest suffix S (say) of P(n) which has previously appeared in P(n). Suppose the most recent appearance of S began at index n-t(n). Then a(n) = t(n), while the length of S is given in A308174.

Original entry on oeis.org

2, 1, 4, 1, 5, 4, 8, 4, 7, 2, 8, 12, 2, 13, 10, 17, 7, 3, 8, 19, 14, 3, 15, 21, 19, 24, 18, 28, 17, 25, 27, 19, 34, 9, 23, 7, 38, 21, 32, 20, 38, 14, 30, 34, 29, 45, 24, 39, 35, 4, 36, 41, 27, 49, 33, 54, 36, 52, 41, 4, 42, 54, 39, 31, 65, 24, 44, 9, 36, 53

Offset: 3

N. J. A. Sloane, May 21 2019, corrected and extended May 21 2019

Then EM(n+1) is the complement of the bit following the most recent appearance of S.

			Tableau showing calculation of terms 3 through 13
1   2   3   4   5   6   7   8   9  10  11  12  13  n
0   1   0   0   1   1   0   1   0   1   1   1   0  A038219(n)
-   -   0   0  01   1  10  01 010 101 011  11 110  S
-   -   1   1   2   1   2   2   3   3   3   2   3  s = A308174(n)
-   -   1   3   1   5   2   4   1   6   4  10   5  previous
-   -   2   1   4   1   5   4   8   4   7   2   8  t = A308175(n)
"Previous" = index of start of most recent previous occurrence of S; s = |S|; t = n - "previous" = A308175(n)

Rémy Sigrist, Table of n, a(n) for n = 3..50000
Rémy Sigrist, Perl program for A308175

Cf. A038219, A308174.

Perl
```
See Links section.
```

More terms from Rémy Sigrist, May 21 2019

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.

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

A308343 a(n) is the difference between the number of zeros and the number of ones among the first n terms of the Ehrenfeucht-Mycielski sequence A038219.

Original entry on oeis.org

1, 0, 1, 2, 1, 0, 1, 0, 1, 0, -1, -2, -1, 0, 1, 0, 1, 2, 3, 4, 3, 2, 1, 0, 1, 0, -1, 0, 1, 0, 1, 0, 1, 2, 1, 2, 3, 2, 1, 0, 1, 0, 1, 2, 3, 2, 1, 2, 3, 4, 5, 6, 5, 6, 5, 4, 5, 4, 3, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1, 0, -1, -2, -3, -4, -3, -4, -3, -4, -3, -4, -5, -4

Offset: 1

Rémy Sigrist, May 21 2019

sign

			The first terms, alongside the numbers of zeros and of ones and A038219(n), are:
  n   a(n)  #0's  #1's  A038219(n)
  --  ----  ----  ----  ----------
   1     1     1     0           0
   2     0     1     1           1
   3     1     2     1           0
   4     2     3     1           0
   5     1     3     2           1
   6     0     3     3           1
   7     1     4     3           0
   8     0     4     4           1
   9     1     5     4           0
  10     0     5     5           1
  11    -1     5     6           1
  12    -2     5     7           1

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, Scatterplot of the first 500000 terms
Rémy Sigrist, Perl program for A308343

Cf. A038219.

Perl
```
See Links section.
```

a(n) = Sum_{k = 1..n} (-1)^A038219(k).

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

cp's OEIS Frontend

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

A201881 Run lengths in maximally unpredictable sequences A007061, A038219.

Views

Author

Keywords

Comments

Examples

Links

Programs

Haskell

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Perl

Extensions

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Perl

Extensions

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

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

A308343 a(n) is the difference between the number of zeros and the number of ones among the first n terms of the Ehrenfeucht-Mycielski sequence A038219.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Perl

Formula