A323595 - OEIS

%I #15 Apr 05 2022 03:19:18

%S 1,2,4,6,10,14,21,28,39,51,69,86,111,138,176,214,264,315,385,454,546,

%T 641,763,881,1032,1188,1385,1580,1824,2066,2371,2668,3037,3413,3869,

%U 4310,4846,5387,6045

%N Number of distinct sets of lengths of nonempty palindrome prefixes, over all binary words of length n.

%e For n = 4, the 6 possible sets are:

%e {1}, corresponding to 0111.

%e {1,2}, corresponding to 0011.

%e {1,3}, corresponding to 0101.

%e {1,4}, corresponding to 0110.

%e {1,2,3}, corresponding to 0001.

%e {1,2,3,4}, corresponding to 0000.

%o (Python)

%o from itertools import product

%o def ispal(w): return w == w[::-1]

%o def pls(w): return tuple(i for i in range(len(w)) if ispal(w[:i+1]))

%o def a(n):  # only search strings starting with 0 by symmetry

%o     return len(set(pls("0"+"".join(u)) for u in product("01", repeat=n-1)))

%o print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Apr 03 2022

%K nonn,more

%O 1,2

%A _Jeffrey Shallit_, Jan 18 2019

%E a(23)-a(39) from _Lars Blomberg_, Feb 21 2019