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 #125 Dec 06 2020 01:36:24
%S 1,1,2,2,4,4,7,7,11,12,18,17,25,27,38,38,50,51,70,69,92,95,122,118,
%T 151,156,197,195,244,242,305,297,369,376,456,441,536,541,658,643,767,
%U 761,920,895,1074,1079,1271,1227,1444,1436,1696,1665,1948,1923,2258,2190
%N Number of distinct sets of palindrome prefix lengths, over all binary palindromes of length n.
%H Michael S. Branicky, <a href="/A304178/b304178.txt">Table of n, a(n) for n = 1..64</a>
%e For n = 7, the possible sets are
%e {1,2,3,4,5,6,7} for the string 0000000,
%e {1,3,5,7} for the string 0101010,
%e {1,2,3,7} for the string 0001000,
%e {1,2,7} for the string 0010100,
%e {1,3,7} for the string 0100010,
%e {1,4,7} for the string 0110110,
%e {1,7} for the string 0111110.
%o (Python)
%o from itertools import product
%o def pals(n):
%o for p in product("01", repeat=n//2):
%o left = "".join(p)
%o right = left[::-1]
%o if n%2==0: yield left+right
%o else:
%o yield left+"0"+right
%o yield left+"1"+right
%o def pal_prefix_lengths(s): # skip length 1 since it is in all sets
%o return [i for i in range(2, len(s)+1) if s[:i]==(s[:i])[::-1]]
%o def a(n):
%o sets = set()
%o for p in pals(n):
%o if p[0]=="1": break # skip by symmetry
%o sets.add(tuple(pal_prefix_lengths(p)))
%o return len(sets)
%o print([a(n) for n in range(1,41)]) # _Michael S. Branicky_, Dec 05 2020
%K nonn
%O 1,3
%A _Jeffrey Shallit_, Jan 28 2019
%E a(41) and beyond from _Michael S. Branicky_, Dec 05 2020