A225370 Let f(S) = maximal m such that the string S contains two disjoint identical (scattered) substrings of length m ("twins"); a(n) = min f(S) over all binary strings of length n.

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

Offset

1,6

Links

Table of n, a(n) for n=1..20.

Maria Axenovich, Yury Person, and Svetlana Puzynina, A regularity lemma and twins in words, arXiv:1204.2180 [math.CO], 2012; Journal of Combinatorial Theory, Series A, V. 120, Issue 4, 2013, p. 733-743.

Formula

From Michael S. Branicky, Aug 29 2025: (Start)

a(n) = f(n, {0,1}) = f(n, 2, 2) as defined in Axenovich et al. and a(6)..a(20) appear in Table 1, p. 8.

floor(n/2) >= a(n) >= floor(n/3). (End)

Prog

(Python)
from itertools import combinations, product
def ok(u, v):
    i = j = 0
    while i < len(u) and j < len(v):
        if u[i] == v[j]:
            i += 1
        j += 1
    return i == len(u)
def f(s):
    n = len(s)
    for l in range(n//2, n//3, -1):
        for I in combinations(range(n), l):
            u = "".join(s[i] for i in I)
            r = "".join(s[_] for _ in range(n) if _ not in I)
            if ok(u, r): return l
    return n//3
def a(n): return min(f("1"+"".join(s)) for s in product("01", repeat=n-1))
print([a(n) for n in range(1, 14)]) # Michael S. Branicky, Aug 29 2025

Crossrefs

Sequence in context: A341168 A071824 A224921 * A114540 A183142 A121830

Adjacent sequences: A225367 A225368 A225369 * A225371 A225372 A225373

Keyword

nonn,more

Author

N. J. A. Sloane, May 07 2013

Status

approved