

A215244


a(n) is the number of ways of writing the binary expansion of n as a product (or concatenation) of palindromes.


14



1, 1, 1, 2, 2, 2, 2, 4, 4, 3, 3, 3, 4, 3, 4, 8, 8, 5, 4, 5, 5, 5, 4, 6, 8, 5, 5, 6, 8, 6, 8, 16, 16, 9, 7, 9, 8, 6, 6, 10, 10, 6, 8, 8, 7, 7, 7, 12, 16, 9, 7, 10, 8, 8, 8, 11, 16, 10, 10, 11, 16, 12, 16, 32, 32, 17, 13, 17, 13, 11, 11, 18, 15, 11, 10, 10, 12, 9, 11, 20, 20, 11, 10, 11, 13, 13, 10, 16, 14, 9, 10, 12, 13, 11, 13, 24, 32, 17, 13, 18, 14, 11, 12, 19, 16, 10, 13
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

"Product" is used here is the usual sense of combinatorics on words.
The sequence may be arranged into a triangle in which row k contains the 2^k terms [a(2^k), ..., a(2^(k+1)1)]: (1), (1), (1,2), (2,2,2,4), ... The row sums of this triangle appear to be A063782.  R. J. Mathar, Aug 09 2012. I have a proof that A063782 does indeed give the row sums.  N. J. A. Sloane, Aug 10 2012


LINKS



EXAMPLE

a(4)=2 since 4 = 100, and 100 can be written as either 1.0.0 or 1.00.
a(5)=2 from 1.0.1, 101.
a(10)=3 from 1.0.1.0, 1.010, 101.1
Written as a triangle, the sequence is:
1,
1,
1, 2,
2, 2, 2, 4,
4, 3, 3, 3, 4, 3, 4, 8,
8, 5, 4, 5, 5, 5, 4, 6, 8, 5, 5, 6, 8, 6, 8, 16,
16, 9, 7, 9, 8, 6, 6, 10, 10, 6, 8, 8, 7, 7, 7, 12, 16, 9, 7, 10, 8, 8, 8, 11, 16, 10, 10, 11, 16, 12, 16, 32,
...


MAPLE

isPal := proc(L)
local d ;
for d from 1 to nops(L)/2 do
if op(d, L) <> op(d, L) then
return false;
end if;
end do:
return true;
end proc:
A215244L := proc(L)
local a, c;
a := 0 ;
if isPal(L) then
a := 1;
end if;
for c from 1 to nops(L)1 do
if isPal( [op(1..c, L)] ) then
a := a+procname([op(c+1..nops(L), L)]) ;
end if;
end do:
return a;
end proc:
if n = 1 then
1;
else
convert(n, base, 2) ;
A215244L(%) ;
end if;
# Caution: the last procedure applies A215244L to the reverse of the binary expansion of n, which is perfectly OK but might cause a problem if the procedure was used in a different problem.  N. J. A. Sloane, Aug 11 2012


MATHEMATICA

palQ[L_] := SameQ[L, Reverse[L]];
b[L_] := b[L] = Module[{a = palQ[L] // Boole, c}, For[c = 1, c < Length[L], c++, If[palQ[L[[;; c]]], a = a + b[L[[c+1;; ]]]]]; a];
a[n_] := If[n == 1, 1, b[IntegerDigits[n, 2]]];


PROG

(Haskell)
import Data.Map (Map, singleton, (!), insert)
import Data.List (inits, tails)
newtype Bin = Bin [Int] deriving (Eq, Show, Read)
instance Ord Bin where
Bin us <= Bin vs  length us == length vs = us <= vs
 otherwise = length us <= length vs
a215244 n = a215244_list !! n
a215244_list = 1 : f [1] (singleton (Bin [0]) 1) where
f bs m  last bs == 1 = y : f (succ bs) (insert (Bin bs) y m)
 otherwise = f (succ bs) (insert (Bin bs) y m) where
y = fromEnum (pal bs) +
sum (zipWith (\us vs > if pal us then m ! Bin vs else 0)
(init $ drop 1 $ inits bs) (drop 1 $ tails bs))
pal ds = reverse ds == ds
succ [] = [0]; succ (0:ds) = 1 : ds; succ (1:ds) = 0 : succ ds


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



