A304178 Number of distinct sets of palindrome prefix lengths, over all binary palindromes of length n.

1, 1, 2, 2, 4, 4, 7, 7, 11, 12, 18, 17, 25, 27, 38, 38, 50, 51, 70, 69, 92, 95, 122, 118, 151, 156, 197, 195, 244, 242, 305, 297, 369, 376, 456, 441, 536, 541, 658, 643, 767, 761, 920, 895, 1074, 1079, 1271, 1227, 1444, 1436, 1696, 1665, 1948, 1923, 2258, 2190

Offset

1,3

Links

Michael S. Branicky, Table of n, a(n) for n = 1..64

Example

For n = 7, the possible sets are
{1,2,3,4,5,6,7} for the string 0000000,
{1,3,5,7} for the string 0101010,
{1,2,3,7} for the string 0001000,
{1,2,7} for the string 0010100,
{1,3,7} for the string 0100010,
{1,4,7} for the string 0110110,
{1,7} for the string 0111110.

Prog

(Python)
from itertools import product
def pals(n):
    for p in product("01", repeat=n//2):
        left = "".join(p)
        right = left[::-1]
        if n%2==0: yield left+right
        else:
            yield left+"0"+right
            yield left+"1"+right
def pal_prefix_lengths(s): # skip length 1 since it is in all sets
    return [i for i in range(2, len(s)+1) if s[:i]==(s[:i])[::-1]]
def a(n):
    sets = set()
    for p in pals(n):
        if p[0]=="1": break # skip by symmetry
        sets.add(tuple(pal_prefix_lengths(p)))
    return len(sets)
print([a(n) for n in range(1, 41)]) # Michael S. Branicky, Dec 05 2020

Crossrefs

Sequence in context: A339244 A197122 A064410 * A266776 A371514 A363214

Adjacent sequences: A304175 A304176 A304177 * A304179 A304180 A304181

Keyword

nonn

Author

Jeffrey Shallit, Jan 28 2019

Extensions

a(41) and beyond from Michael S. Branicky, Dec 05 2020

Status

approved