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