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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A355520 Number of length-n 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. a(n) is even by symmetry. - Michael S. Branicky, Jul 06 2022 LINKS Table of n, a(n) for n=1..21. 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. 57-71. 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=n-1) if ok("0"+"".join(u))) print([a(n) for n in range(1, 12)]) # Michael S. Branicky, Jul 06 2022 CROSSREFS Cf. A339391, A339668. Sequence in context: A078389 A248847 A059173 * A274005 A027560 A135493 Adjacent sequences: A355517 A355518 A355519 * A355521 A355522 A355523 KEYWORD nonn,more AUTHOR Jeffrey Shallit, Jul 05 2022 EXTENSIONS a(13)-a(18) from Michael S. Branicky, Jul 05 2022 a(19)-a(21) from Michael S. Branicky, Jul 06 2022 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 18 15:05 EDT 2024. Contains 376000 sequences. (Running on oeis4.)