The OEIS is supported by the many generous donors to the OEIS Foundation.

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

1

`%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
`