A355520 - OEIS

%I #27 Jan 14 2023 10:50:03

%S 2,4,8,16,32,62,116,206,350,566,886,1334,1974,2846,3978,5472,7398,

%T 9854,12964,16804,21524

%N Number of length-n binary strings having a string attractor of size at most 2.

%C A string attractor for a string x=x[1..n] is a set of positions S, a subset of {1,2,...,n}, such that every block occurring in x has a (possibly different) occurrence touching one of the positions in S.

%C a(n) is even by symmetry. - _Michael S. Branicky_, Jul 06 2022

%H S. Mantaci, A. Restivo, G. Romana, G. Rosone, and M. Sciortino, <a href="http://ceur-ws.org/Vol-2504/paper8.pdf">String attractors and combinatorics on words</a>, Proc. ICTCS 2019 (20th Italian Conference on Theoretical Computer Science), CEUR Workshop Proceedings, pp. 57-71.

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

%e For example, the string 001011 has no string attractor of size 2, but it does have a string attractor of size 3, namely {1,3,5}.

%o (Python)

%o from itertools import combinations as C, product as P

%o def blocks_ranges(w):

%o     blocks = dict()

%o     for i in range(len(w)):

%o         for j in range(i+1, len(w)+1):

%o             wij = w[i:j]

%o             if wij in blocks: blocks[wij].append(set(range(i, j)))

%o             else: blocks[wij] = [set(range(i, j))]

%o     return blocks

%o def isa(S, w):  # S is an attractor for string w

%o     br = blocks_ranges(w)

%o     for b in br:

%o         for i in range(len(br[b])):

%o             if S & br[b][i]: break

%o         else: return False

%o     return True

%o def ok(w):  # w has a string attractor of size at most 2

%o     return any(isa(set(s), w) for r in (1, 2) for s in C(range(len(w)), r))

%o def a(n):   # only search strings starting with 0 by symmetry

%o     return sum(2 for u in P("01", repeat=n-1) if ok("0"+"".join(u)))

%o print([a(n) for n in range(1, 12)]) # _Michael S. Branicky_, Jul 06 2022

%Y Cf. A339391, A339668.

%K nonn,more

%O 1,1

%A _Jeffrey Shallit_, Jul 05 2022

%E a(13)-a(18) from _Michael S. Branicky_, Jul 05 2022

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