

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**(n1)): # only search 1st bit == 1 by symmetry
LBfacsum += LBfactors((1<<(n1))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



