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|.
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
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Nov 25 2020
EXTENSIONS
a(22)-a(33) from Michael S. Branicky, Nov 28 2020
STATUS
approved