A330886 - OEIS

A330886

Sum of lengths of SB (shortest border) factorizations over all binary strings of length n.

0, 2, 6, 16, 38, 88, 196, 432, 930, 1992, 4204, 8848, 18428, 38320, 79080, 163040, 334214, 684696, 1396516, 2847280, 5785012, 11750928, 23803512, 48210336, 97426708, 196865488, 397086200, 800882848, 1612955736, 3248291552, 6533903248, 13142446784, 26409360962, 53067656712, 106550428268, 213931086224

(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 SB ("shortest 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 shortest border of w, and repeat with w'. The length of the factorization is the number of factors. For example, 011011101 = (01)(1)(011)(1)(01), and so the factorization has length 5.

Asymptotically C*2^n, for C = 6.468626906... .

LINKS

Table of n, a(n) for n=0..35.

Ragnar Groot Koerkamp and Timon Knigge, Isomorphic inversion problem, 2018.

"Slashadam" Reddit user, Palindromity function, April 29 2020.

CROSSREFS

Cf. A330884.

Sequence in context: A167821 A093041 A156616 * A265758 A265107 A217631

Adjacent sequences: A330883 A330884 A330885 * A330887 A330888 A330889

KEYWORD

nonn

AUTHOR

Jeffrey Shallit, Apr 30 2020

EXTENSIONS

a(28)-a(35) from Bert Dobbelaere, May 12 2020

STATUS

approved