

A339668


Number of lengthn binary strings having minimum string attractor size 2.


0



0, 2, 6, 14, 30, 60, 114, 204, 348, 564, 884, 1332, 1972, 2844, 3976, 5470, 7396, 9852, 12962, 16802
(list;
graph;
refs;
listen;
history;
text;
internal format)



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

Table of n, a(n) for n=1..20.
D. Kempa and N. Prezza. At the roots of dictionary compression: string attractors. In STOCâ€™18 Proceedings, ACM Press, 2018, pp. 827840.


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=n1))
print([a(n) for n in range(1, 12)]) # Michael S. Branicky, Dec 20 2020


CROSSREFS

Cf. A339391.
Sequence in context: A072611 A284023 A192966 * A260058 A331699 A327048
Adjacent sequences: A339665 A339666 A339667 * A339669 A339670 A339671


KEYWORD

nonn,more


AUTHOR

Jeffrey Shallit, Dec 12 2020


EXTENSIONS

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


STATUS

approved



