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
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
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Dec 19 2020
EXTENSIONS
a(16)-a(18) from Michael S. Branicky, Dec 20 2020
STATUS
approved
