%I #19 Jul 28 2021 14:03:08
%S 0,2,4,6,20,32,88,162,360,758,1564,3290,6692,13898,28356,57954,117948,
%T 239378,485472,981374,1982324,3997004,8051432,16201164,32570108,
%U 65431734,131358932,263572810,528600668,1059691960,2123635312,4254511910,8521368640,17063718174,34163130608
%N Number of binary strings of length n having a factorization as a concatenation of palindromes of length at least 2.
%e a(4) = 6 because {0000, 0011, 0110, 1001, 1100, 1111} are factorizable into palindromes of length >= 2.
%e Terms are even by symmetry. - _Michael S. Branicky_, Jul 28 2021
%o (Python)
%o from functools import lru_cache
%o def ispal(s): return s == s[::-1]
%o @lru_cache(maxsize=None)
%o def ok(b): # takes a binary string
%o if len(b) >= 2 and ispal(b): return True
%o for i in range(2, len(b)-1):
%o if ispal(b[:i]) and ok(b[i:]): return True
%o return False
%o def a(n): return 2*sum(1 for m in range(2**(n-1), 2**n) if ok(bin(m)[2:]))
%o print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Jul 28 2021
%Y Cf. A241208, A241211.
%K nonn,more
%O 1,2
%A _Jeffrey Shallit_, Apr 17 2014
%E a(17)-a(30) from _Giovanni Resta_, Apr 18 2014
%E a(31)-a(35) from _Michael S. Branicky_, Jul 28 2021
|