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

%I #61 Oct 27 2019 11:13:15

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

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

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

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

%C "Product" is used here is the usual sense of combinatorics on words.

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

%C a(A220654(n)) = n and a(m) < n for m < A220654(n). - _Reinhard Zumkeller_, Dec 17 2012

%H N. J. A. Sloane, <a href="/A215244/b215244.txt">Table of n, a(n) for n = 0..10000</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%H <a href="/index/Pac#palindromes">Index entries for sequences related to palindromes</a>

%e a(4)=2 since 4 = 100, and 100 can be written as either 1.0.0 or 1.00.

%e a(5)=2 from 1.0.1, 101.

%e a(10)=3 from 1.0.1.0, 1.010, 101.1

%e Written as a triangle, the sequence is:

%e 1,

%e 1,

%e 1, 2,

%e 2, 2, 2, 4,

%e 4, 3, 3, 3, 4, 3, 4, 8,

%e 8, 5, 4, 5, 5, 5, 4, 6, 8, 5, 5, 6, 8, 6, 8, 16,

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

%e ...

%p isPal := proc(L)

%p local d ;

%p for d from 1 to nops(L)/2 do

%p if op(d,L) <> op(-d,L) then

%p return false;

%p end if;

%p end do:

%p return true;

%p end proc:

%p A215244L := proc(L)

%p local a,c;

%p a := 0 ;

%p if isPal(L) then

%p a := 1;

%p end if;

%p for c from 1 to nops(L)-1 do

%p if isPal( [op(1..c,L)] ) then

%p a := a+procname([op(c+1..nops(L),L)]) ;

%p end if;

%p end do:

%p return a;

%p end proc:

%p A215244 := proc(n)

%p if n = 1 then

%p 1;

%p else

%p convert(n,base,2) ;

%p A215244L(%) ;

%p end if;

%p end proc: # _R. J. Mathar_, Aug 07 2012

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

%t palQ[L_] := SameQ[L, Reverse[L]];

%t 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];

%t a[n_] := If[n == 1, 1, b[IntegerDigits[n, 2]]];

%t a /@ Range[0, 106] (* _Jean-François Alcover_, Oct 27 2019 *)

%o (Haskell)

%o import Data.Map (Map, singleton, (!), insert)

%o import Data.List (inits, tails)

%o newtype Bin = Bin [Int] deriving (Eq, Show, Read)

%o instance Ord Bin where

%o Bin us <= Bin vs | length us == length vs = us <= vs

%o | otherwise = length us <= length vs

%o a215244 n = a215244_list !! n

%o a215244_list = 1 : f [1] (singleton (Bin [0]) 1) where

%o f bs m | last bs == 1 = y : f (succ bs) (insert (Bin bs) y m)

%o | otherwise = f (succ bs) (insert (Bin bs) y m) where

%o y = fromEnum (pal bs) +

%o sum (zipWith (\us vs -> if pal us then m ! Bin vs else 0)

%o (init $ drop 1 $ inits bs) (drop 1 $ tails bs))

%o pal ds = reverse ds == ds

%o succ [] = [0]; succ (0:ds) = 1 : ds; succ (1:ds) = 0 : succ ds

%o -- _Reinhard Zumkeller_, Dec 17 2012

%Y Cf. A050430, A215245, A215246, A215250, A215253, A215254, A063782.

%Y Cf. A206925, A030308.

%K nonn,base,look

%O 0,4

%A _N. J. A. Sloane_, Aug 07 2012