VOOZH about

URL: https://oeis.org/A241210

⇱ A241210 - OEIS

login
A241210
Number of binary strings of length n having a factorization as a concatenation of palindromes of length at least 2.
4
0, 2, 4, 6, 20, 32, 88, 162, 360, 758, 1564, 3290, 6692, 13898, 28356, 57954, 117948, 239378, 485472, 981374, 1982324, 3997004, 8051432, 16201164, 32570108, 65431734, 131358932, 263572810, 528600668, 1059691960, 2123635312, 4254511910, 8521368640, 17063718174, 34163130608
OFFSET
1,2
EXAMPLE
a(4) = 6 because {0000, 0011, 0110, 1001, 1100, 1111} are factorizable into palindromes of length >= 2.
Terms are even by symmetry. - Michael S. Branicky, Jul 28 2021
PROG
(Python)
from functools import lru_cache
def ispal(s): return s == s[::-1]
@lru_cache(maxsize=None)
def ok(b): # takes a binary string
if len(b) >= 2 and ispal(b): return True
for i in range(2, len(b)-1):
if ispal(b[:i]) and ok(b[i:]): return True
return False
def a(n): return 2*sum(1 for m in range(2**(n-1), 2**n) if ok(bin(m)[2:]))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Jul 28 2021
CROSSREFS
Sequence in context: A108439 A245766 A193774 * A333992 A176652 A251724
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Apr 17 2014
EXTENSIONS
a(17)-a(30) from Giovanni Resta, Apr 18 2014
a(31)-a(35) from Michael S. Branicky, Jul 28 2021
STATUS
approved