login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A339668 Number of length-n binary strings having minimum string attractor size 2. 0
0, 2, 6, 14, 30, 60, 114, 204, 348, 564, 884, 1332, 1972, 2844, 3976, 5470, 7396, 9852, 12962, 16802 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

Table of n, a(n) for n=1..20.

D. Kempa and N. Prezza. At the roots of dictionary compression: string attractors. In STOC’18 Proceedings, ACM Press, 2018, pp. 827-840.

PROG

(Python) # needs subroutines in A339391

from itertools import product, combinations

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

  for r in range(1, 3):

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

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

  return False

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

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

print([a(n) for n in range(1, 12)]) # Michael S. Branicky, Dec 20 2020

CROSSREFS

Cf. A339391.

Sequence in context: A072611 A284023 A192966 * A260058 A331699 A327048

Adjacent sequences:  A339665 A339666 A339667 * A339669 A339670 A339671

KEYWORD

nonn,more

AUTHOR

Jeffrey Shallit, Dec 12 2020

EXTENSIONS

a(19)-a(20) from Michael S. Branicky, Dec 20 2020

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 15 02:21 EDT 2021. Contains 343909 sequences. (Running on oeis4.)