A339149 - OEIS

%I #20 Jan 08 2021 22:04:15

%S 0,2,6,18,38,98,198,442,904,1928,3858,8050,16102,32878,65926,133430,

%T 266862,537692,1075386,2159044,4318990,8656396,17312794,34668432,

%U 69337016,138763784,277532124,555260052,1110520106,2221474736,4442949474,8886812452,17773647430

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

%C 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|.

%o (Python)

%o from itertools import product

%o def sc(v):

%o     best = 0

%o     for y in (v[-i:] for i in range(1, len(v)//2+1)):

%o         for t in range(2, len(v)//len(y)+1):

%o             if not v.endswith(y*t): break

%o             best = max(best, (t-1)*len(y))

%o     return best

%o def a(n): # by symmetry, twice that of starting with "0"

%o     return 2*sum(sc("0"+"".join(b)) for b in product("01", repeat=n-1))

%o print([a(n) for n in range(1,21)]) # _Michael S. Branicky_, Nov 28 2020

%Y Cf. A036289.

%K nonn

%O 1,2

%A _Jeffrey Shallit_, Nov 25 2020

%E a(22)-a(33) from _Michael S. Branicky_, Nov 28 2020