A330881 Length of longest LB factorization over all binary strings of length n.

0, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9, 10, 11, 11, 11, 12, 13, 14, 15, 16, 17, 17, 17, 18, 19, 20, 21, 22, 23, 23, 23, 24, 25, 26, 27, 28, 29, 29, 29, 30, 31, 32, 33, 34, 35, 35, 35, 36, 37, 38, 39, 40, 41, 41, 41, 42, 43, 44, 45, 46, 47, 47, 47, 48, 49, 50, 51, 52

Offset

0,3

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

Colin Barker, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (2,-2,2,-2,2,-2,2,-1).

Formula

For n >= 0, we have a(8n+i) = 6n+i for 0 <= i <= 5, and a(8n+6) = a(8n+7) = 6n+5.

From Colin Barker, May 01 2020: (Start)

G.f.: x*(1 + x^2 + x^4 - x^5 + x^6) / ((1 - x)^2*(1 + x^2)*(1 + x^4)).

a(n) = 2*a(n-1) - 2*a(n-2) + 2*a(n-3) - 2*a(n-4) + 2*a(n-5) - 2*a(n-6) + 2*a(n-7) - a(n-8) for n>7.

(End)

Example

For n = 7 an example achieving a(7) = 5 is 0101100 = (0)(10)(1)(10)(0).

Prog

(PARI) concat(0, Vec((1 + x^2 + x^4 - x^5 + x^6)/((-1 + x)^2*(1 + x^2 + x^4 + x^6)) + O(x^70))) \\ Jinyuan Wang, May 01 2020

Crossrefs

Cf. A330882, A330884.

Sequence in context: A347762 A270432 A007599 * A279317 A362626 A362471

Adjacent sequences: A330878 A330879 A330880 * A330882 A330883 A330884

Keyword

nonn,easy

Author

Jeffrey Shallit, Apr 30 2020

Extensions

More terms from Jinyuan Wang, May 01 2020

Status

approved