A309077 Maximum sum of base lengths over all minimal factorizations of length-n binary strings.

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, 18, 18, 19, 20, 20, 21, 22, 22, 23, 23, 24, 25, 25

Offset

1,2

Comments

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.

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.

Upper bound for sufficiently large n reduced to a(n) < 0.621 n considering a(29) = 18. - Bert Dobbelaere, Jul 21 2019

Links

Table of n, a(n) for n=1..40.

Formula

a(j+k) <= a(j) + a(k). - Bert Dobbelaere, Jul 21 2019

Example

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).

Crossrefs

Cf. A309078.

Sequence in context: A073869 A060143 A005206 * A057365 A014245 A350969

Adjacent sequences: A309074 A309075 A309076 * A309078 A309079 A309080

Keyword

nonn,more

Author

Jeffrey Shallit, Jul 11 2019

Extensions

a(21)-a(40) from Bert Dobbelaere, Jul 21 2019

Status

approved