

A355520


Number of lengthn binary strings having a string attractor of size at most 2.


1



2, 4, 8, 16, 32, 62, 116, 206, 350, 566, 886, 1334, 1974, 2846, 3978, 5472, 7398, 9854, 12964, 16804, 21524
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

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.


LINKS

S. Mantaci, A. Restivo, G. Romana, G. Rosone, and M. Sciortino, String attractors and combinatorics on words, Proc. ICTCS 2019 (20th Italian Conference on Theoretical Computer Science), CEUR Workshop Proceedings, pp. 5771.


FORMULA

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


EXAMPLE

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


PROG

(Python)
from itertools import combinations as C, product as P
def blocks_ranges(w):
blocks = dict()
for i in range(len(w)):
for j in range(i+1, len(w)+1):
wij = w[i:j]
if wij in blocks: blocks[wij].append(set(range(i, j)))
else: blocks[wij] = [set(range(i, j))]
return blocks
def isa(S, w): # S is an attractor for string w
br = blocks_ranges(w)
for b in br:
for i in range(len(br[b])):
if S & br[b][i]: break
else: return False
return True
def ok(w): # w has a string attractor of size at most 2
return any(isa(set(s), w) for r in (1, 2) for s in C(range(len(w)), r))
def a(n): # only search strings starting with 0 by symmetry
return sum(2 for u in P("01", repeat=n1) if ok("0"+"".join(u)))


CROSSREFS



KEYWORD

nonn,more


AUTHOR



EXTENSIONS



STATUS

approved



