A339357 Number of different profiles of sizes of smallest string attractors, over all binary strings of length n.

1, 2, 3, 4, 5, 7, 11, 17, 26, 39, 60, 97, 163, 271, 458, 760, 1255, 2105

Offset

1,2

Comments

A string attractor for a string w is a set S of positions in w such that every factor (i.e., contiguous subblock within w) touches at least one of the positions in S. The string attractor profile for a string w is the size of the smallest string attractor for each nonempty prefix of w. For example, for the string 00101101, the string attractor profile is (1, 1, 2, 2, 2, 3, 3, 2). This sequence counts the different profiles.

Links

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

S. Mantaci, A. Restivo, G. Romana, G. Rosone, and M. Sciortino, A combinatorial view of string attractors, Theor. Comput. Sci. 850 (2021) 236-248.

Prog

(Python)  # needs subroutines in A339391
from itertools import product
def lsa_profile(w):
    return tuple(lsa(w[:i]) for i in range(1, len(w) + 1))
def a(n):  # only search strings starting with 0 by symmetry
    profiles = set()
    for u in product("01", repeat=n - 1):
        profiles.add(lsa_profile("0" + "".join(u)))
    return len(profiles)
print([a(n) for n in range(1, 11)])  # Michael S. Branicky, Dec 20 2020

Crossrefs

Cf. A339391.

Sequence in context: A143284 A343305 A346076 * A279065 A327325 A340252

Adjacent sequences: A339354 A339355 A339356 * A339358 A339359 A339360

Keyword

nonn,more

Author

Jeffrey Shallit, Dec 19 2020

Extensions

a(16)-a(18) from Michael S. Branicky, Dec 20 2020

Status

approved