A093383 -id:A093383 - cp's OEIS frontend

A093382 a(n) = length k of longest binary sequence x(1) ... x(k) such that for no n <= i < j <= k/2 is x(i) ... x(2i) a subsequence of x(j) ... x(2j).

11, 31, 199

Offset: 1

N. J. A. Sloane, Apr 29 2004

Doesn't the binary sequence 000010011001110011101010101010101010101100110 demonstrate that a(2) >= 45? - R. J. Mathar, Jul 29 2007 Answer: No - see the following comment.
The sequence of length 45 above does not satisfy the requirements of the definition: Subsequences are not required to be consecutive. Therefore it cannot show a(2) >= 45. In the sequence we find for i=2, j=3: x(i..2i) is 000; x(j..2j) is 001001; and 000 is a subsequence of 001001. - Don Reble, May 13 2008
a(4) >= 376843. - Bert Dobbelaere, May 25 2024

			a(1) = 11 from 01110000000.

a(1) - a(3) computed by R. Dougherty, who finds that a(4) >= 187205.

H. M. Friedman, Long finite sequences, J. Comb. Theory, A 95 (2001), 102-144.

See A093383-A093386 for illustrations of a(2) and a(3). Cf. A014221, A094091.

A094091 a(1) = 0; for n>0, a(n) = smaller of 0 and 1 such that we avoid the property that, for some i and j in the range S = 2 <= i < j <= n/2, a(i) ... a(2i) is a subsequence of a(j) ... a(2j).

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, May 02 2004

A greedy version of A093383 and A093384.
This is a finite sequence of length 23 (necessarily <= A093382(2) = 31).
For S >= 1 define a sequence by a(1) = 0; for n>0, a(n) = smaller of 0 and 1 such that we avoid the property that, for some i and j in the range S <= i < j <= n/2, a(i) ... a(2i) is a subsequence of a(j) ... a(2j). The present sequence is the case S=2. For S=1 we get a sequence of length 3, namely 0,0,0, and A096094, A106197 are the cases S=3 and S=4. A093382(S) gives an upper bound on their lengths.

			After a(1) = a(2) = a(3) = a(4) = 0 we must have a(5) = 1, or else we would have a(2)a(3)a(4) = 000 as a subsequence of a(3)a(4)a(5)a(6) = 000a(6).

H. M. Friedman, Long finite sequences, J. Comb. Theory, A 95 (2001), 102-144.

Cf. A093382, A093383, A093384, A096094, A106197.

The remaining terms, a(17)-a(23), were sent by Joshua Zucker, Jul 23 2006

cp's OEIS Frontend

A093382 a(n) = length k of longest binary sequence x(1) ... x(k) such that for no n <= i < j <= k/2 is x(i) ... x(2i) a subsequence of x(j) ... x(2j).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs