OFFSET

1,2

COMMENTS

A set S of positions of a string w[1..n] is called a "string attractor" if every nonempty contiguous block occurring in w has an occurrence in w that touches at least one of the positions of S. For example, "alfalfa" has a string attractor of size 3: {3,4,5}.

LINKS

D. Kempa and N. Prezza. At the roots of dictionary compression: string attractors. In STOCâ€™18 Proceedings, ACM Press, 2018, pp. 827-840.

FORMULA

a(n) = A355520(n) - 2, since only 0^n and 1^n possess string attractors of size 1. - Michael S. Branicky, Jul 06 2022

PROG

(Python) # needs subroutines in A339391

from itertools import product, combinations

def lsa_is_2(w): # length of smallest attractor of w is 2

for r in range(1, 3):

for s in combinations(range(len(w)), r):

if is_attractor(set(s), w): return r == 2

return False

def a(n): # twice value of strings starting with 0 by symmetry

return 2*sum(lsa_is_2("0"+"".join(u)) for u in product("01", repeat=n-1))

print([a(n) for n in range(1, 12)]) # Michael S. Branicky, Dec 20 2020

CROSSREFS

KEYWORD

nonn,more

AUTHOR

Jeffrey Shallit, Dec 12 2020

EXTENSIONS

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

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

STATUS

approved