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

%I #26 May 12 2020 16:27:01

%S 0,2,6,16,38,88,196,432,930,1992,4204,8848,18428,38320,79080,163040,

%T 334214,684696,1396516,2847280,5785012,11750928,23803512,48210336,

%U 97426708,196865488,397086200,800882848,1612955736,3248291552,6533903248,13142446784,26409360962,53067656712,106550428268,213931086224

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

%C 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.

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

%H Ragnar Groot Koerkamp and Timon Knigge, <a href="https://open.kattis.com/problems/isomorphicinversion">Isomorphic inversion problem</a>, 2018.

%H "Slashadam" Reddit user, <a href="https://old.reddit.com/r/math/comments/ga2iyo/i_just_defined_the_palindromity_function_on/">Palindromity function</a>, April 29 2020.

%Y Cf. A330884.

%K nonn

%O 0,2

%A _Jeffrey Shallit_, Apr 30 2020

%E a(28)-a(35) from _Bert Dobbelaere_, May 12 2020