login
A339149
Sum of the lengths of degree of suffix compression achieved for all binary strings of length n.
0
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|.
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 A376739 A364672
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Nov 25 2020
EXTENSIONS
a(22)-a(33) from Michael S. Branicky, Nov 28 2020
STATUS
approved