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