Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the 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