A355520 Number of length-n binary strings having a string attractor of size at most 2.

2, 4, 8, 16, 32, 62, 116, 206, 350, 566, 886, 1334, 1974, 2846, 3978, 5472, 7398, 9854, 12964, 16804, 21524

Offset

1,1

Comments

A string attractor for a string x=x[1..n] is a set of positions S, a subset of {1,2,...,n}, such that every block occurring in x has a (possibly different) occurrence touching one of the positions in S.

a(n) is even by symmetry. - Michael S. Branicky, Jul 06 2022

Links

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

S. Mantaci, A. Restivo, G. Romana, G. Rosone, and M. Sciortino, String attractors and combinatorics on words, Proc. ICTCS 2019 (20th Italian Conference on Theoretical Computer Science), CEUR Workshop Proceedings, pp. 57-71.

Formula

a(n) = A339668(n) + 2, since only 0^n and 1^n possess string attractors of size 1, where ^ is repeated concatenation. - Michael S. Branicky, Jul 06 2022

Example

For example, the string 001011 has no string attractor of size 2, but it does have a string attractor of size 3, namely {1,3,5}.

Prog

(Python)
from itertools import combinations as C, product as P
def blocks_ranges(w):
    blocks = dict()
    for i in range(len(w)):
        for j in range(i+1, len(w)+1):
            wij = w[i:j]
            if wij in blocks: blocks[wij].append(set(range(i, j)))
            else: blocks[wij] = [set(range(i, j))]
    return blocks
def isa(S, w):  # S is an attractor for string w
    br = blocks_ranges(w)
    for b in br:
        for i in range(len(br[b])):
            if S & br[b][i]: break
        else: return False
    return True
def ok(w):  # w has a string attractor of size at most 2
    return any(isa(set(s), w) for r in (1, 2) for s in C(range(len(w)), r))
def a(n):   # only search strings starting with 0 by symmetry
    return sum(2 for u in P("01", repeat=n-1) if ok("0"+"".join(u)))
print([a(n) for n in range(1, 12)]) # Michael S. Branicky, Jul 06 2022

Crossrefs

Cf. A339391, A339668.

Sequence in context: A078389 A248847 A059173 * A274005 A027560 A135493

Adjacent sequences: A355517 A355518 A355519 * A355521 A355522 A355523

Keyword

nonn,more

Author

Jeffrey Shallit, Jul 05 2022

Extensions

a(13)-a(18) from Michael S. Branicky, Jul 05 2022

a(19)-a(21) from Michael S. Branicky, Jul 06 2022

Status

approved