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