A339668 - OEIS

%I #21 Jul 07 2022 02:03:37

%S 0,2,6,14,30,60,114,204,348,564,884,1332,1972,2844,3976,5470,7396,

%T 9852,12962,16802,21522

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

%C 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}.

%H D. Kempa and N. Prezza. <a href="https://dl.acm.org/doi/abs/10.1145/3188745.3188814">At the roots of dictionary compression: string attractors</a>. In STOC’18 Proceedings, ACM Press, 2018, pp. 827-840.

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

%o (Python) # needs subroutines in A339391

%o from itertools import product, combinations

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

%o   for r in range(1, 3):

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

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

%o   return False

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

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

%o print([a(n) for n in range(1, 12)]) # _Michael S. Branicky_, Dec 20 2020

%Y Cf. A339391, A355520.

%K nonn,more

%O 1,2

%A _Jeffrey Shallit_, Dec 12 2020

%E a(19)-a(20) from _Michael S. Branicky_, Dec 20 2020

%E a(21) from _Michael S. Branicky_, Jul 06 2022