Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #24 Sep 26 2019 04:18:54
%S 1,2,3,3,4,4,5,6,6,7,8,8,9,9,10,11,11,12,13,13,14,14,15,16,16,17,17,
%T 18,18,19,20,20,21,22,22,23,23,24,25,25
%N Maximum sum of base lengths over all minimal factorizations of length-n binary strings.
%C A factorization of a binary string x is an expression of the form prod_i w_i^{e_i}, where each w_i is a word and e_i is an integer exponent specifying how many times the word is repeated. For example 0101000 = (01)^2 0^3. A minimal factorization is one that minimizes the weight of the factorization, which is defined to be sum of the lengths of the w_i. a(n) then measures the maximum weight over all length-n binary strings.
%C Since there are arbitrarily long binary words having no repetitions larger than squares (Thue 1906), we see that a(n) >= n/2. By considering a(14) = 9, and splitting a word into blocks of size 14 and one left over, we see that a(n) <= 0.644 n for sufficiently large n.
%C Upper bound for sufficiently large n reduced to a(n) < 0.621 n considering a(29) = 18. - _Bert Dobbelaere_, Jul 21 2019
%F a(j+k) <= a(j) + a(k). - _Bert Dobbelaere_, Jul 21 2019
%e For n = 8, we have a(8) = 6, and a word that achieves the maximum is 01001101, where the corresponding weight-6 factorization is (01) 0^2 1^2 (01).
%Y Cf. A309078.
%K nonn,more
%O 1,2
%A _Jeffrey Shallit_, Jul 11 2019
%E a(21)-a(40) from _Bert Dobbelaere_, Jul 21 2019