A330884 Sum of the lengths of LB factorizations over all binary strings of length n.

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

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