A330881 - OEIS

%I #19 May 01 2020 12:11:16

%S 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,

%T 21,22,23,23,23,24,25,26,27,28,29,29,29,30,31,32,33,34,35,35,35,36,37,

%U 38,39,40,41,41,41,42,43,44,45,46,47,47,47,48,49,50,51,52

%N Length of longest LB factorization 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 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.

%H Colin Barker, <a href="/A330881/b330881.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (2,-2,2,-2,2,-2,2,-1).

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

%F From _Colin Barker_, May 01 2020: (Start)

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

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

%F (End)

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

%o (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

%Y Cf. A330882, A330884.

%K nonn,easy

%O 0,3

%A _Jeffrey Shallit_, Apr 30 2020

%E More terms from _Jinyuan Wang_, May 01 2020