A339149 Sum of the lengths of degree of suffix compression achieved for all binary strings of length n.

0, 2, 6, 18, 38, 98, 198, 442, 904, 1928, 3858, 8050, 16102, 32878, 65926, 133430, 266862, 537692, 1075386, 2159044, 4318990, 8656396, 17312794, 34668432, 69337016, 138763784, 277532124, 555260052, 1110520106, 2221474736, 4442949474, 8886812452, 17773647430

Offset

1,2

Comments

A suffix compression for a string v is xy, where v = x y^t for strings x, y and a nonnegative integer t. For example, a suffix compression of abcdedede is (abc)(de). The degree of suffix compression is thus the maximum amount saved, namely, |xy^t| - |xy| = (t-1) |y|.

Links

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

Prog

(Python)
from itertools import product
def sc(v):
    best = 0
    for y in (v[-i:] for i in range(1, len(v)//2+1)):
        for t in range(2, len(v)//len(y)+1):
            if not v.endswith(y*t): break
            best = max(best, (t-1)*len(y))
    return best
def a(n): # by symmetry, twice that of starting with "0"
    return 2*sum(sc("0"+"".join(b)) for b in product("01", repeat=n-1))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Nov 28 2020

Crossrefs

Cf. A036289.

Sequence in context: A302647 A324580 A338765 * A101695 A364672 A014741

Adjacent sequences: A339146 A339147 A339148 * A339150 A339151 A339152

Keyword

nonn

Author

Jeffrey Shallit, Nov 25 2020

Extensions

a(22)-a(33) from Michael S. Branicky, Nov 28 2020

Status

approved