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!)
A330884 Sum of the lengths of LB factorizations over all binary strings of length n. 4
0, 2, 6, 16, 34, 80, 164, 368, 754, 1640, 3312, 7064, 14312, 30088, 60612, 126104, 253918, 524104, 1053564, 2161376, 4341072, 8863048, 17786736, 36176784, 72556592, 147125256, 294927876, 596566200, 1195391736, 2413163552, 4833869604, 9742379496, 19509908190, 39268751168, 78621406744, 158073043176 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

A border of a string w is a nonempty proper prefix of w that is also a suffix.  The LB ("longest border") factorization of a string w is as follows:  if w has no border, then the factorization is just (w).  Otherwise, write w = (x)(w')(x) where x is the longest border of length <= |w|/2, and continue with w'.   The length of the factorization is the number of factors.  For example, 0101101010 = (010)(1)(10)(1)(010), and so has length 5.

LINKS

Michael S. Branicky, Table of n, a(n) for n = 0..41

PROG

(Python) # LBfactors() in A330882

from numba import njit

@njit()  # comment out for n > 64

def a(n):

  if n <= 1: return 2*n

  LBfacsum = 0

  for i in range(2**(n-1)):  # only search 1st bit == 1 by symmetry

    LBfacsum += LBfactors((1<<(n-1))|i, n)

  return 2*LBfacsum     # symmetry

print([a(n) for n in range(25)]) # Michael S. Branicky, Dec 31 2020

CROSSREFS

Cf. A330881, A330882.

Sequence in context: A248832 A280400 A199477 * A060354 A140131 A159938

Adjacent sequences:  A330881 A330882 A330883 * A330885 A330886 A330887

KEYWORD

nonn

AUTHOR

Jeffrey Shallit, Apr 30 2020

EXTENSIONS

a(28)-a(35) from Bert Dobbelaere, May 12 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 August 3 21:46 EDT 2021. Contains 346441 sequences. (Running on oeis4.)