A339668 Number of length-n binary strings having minimum string attractor size 2.

0, 2, 6, 14, 30, 60, 114, 204, 348, 564, 884, 1332, 1972, 2844, 3976, 5470, 7396, 9852, 12962, 16802, 21522

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..21.

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

Cf. A339391, A355520.

Sequence in context: A284023 A366542 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

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

Status

approved