A215253 -id:A215253 - cp's OEIS frontend

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

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

Offset: 0

N. J. A. Sloane, Aug 07 2012

"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
a(A220654(n)) = n and a(m) < n for m < A220654(n). - Reinhard Zumkeller, Dec 17 2012

			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,
...

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

Cf. A206925, A030308.

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
-- Reinhard Zumkeller, Dec 17 2012

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:
A215244 := proc(n)
    if n = 1 then
        1;
    else
        convert(n,base,2) ;
        A215244L(%) ;
    end if;
end proc: # R. J. Mathar, Aug 07 2012
# 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

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]]];
a /@ Range[0, 106] (* Jean-François Alcover, Oct 27 2019 *)

A215246 a(n) = maximal value of k such that A215244(k) = n.

Original entry on oeis.org

2, 6, 13, 22, 26, 41, 50, 54, 89, 105, 101, 109, 178, 166, 118, 185, 217, 218, 201, 357, 361, 358, 422, 329, 434, 425, 429, 418, 617, 441, 666, 717, 845, 722, 745, 741, 718, 873, 869, 841, 846, 1430, 882, 844, 866, 934, 946, 1446, 1434, 885, 1690, 1625, 1445, 1686, 949, 1714, 1497

Offset: 1

N. J. A. Sloane, Aug 07 2012

			A215244(k) = 4 for k = 7,8,12,14,18,22, so a(4) = 22.

N. J. A. Sloane, Table of n, a(n) for n = 1..307

Cf. A215244, A215245, A215253, A215254.

# Since A214245(12)=95, the following program gives correct values for a(n) for n <= 94.
A215246:=proc(M) local lis,n,p,i;
lis:=array(1..1024);
for n from 1 to M do
p:=A215244(n);
if p <= 1024 then lis[p]:=n; fi;
                  od;
[seq(lis[i],i=1..94)];
end proc;
A215246(2^12 - 1);

A215245 a(n) = minimal value of A215244(k) for 2^n <= k < 2^(n+1).

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 9, 13, 20, 29, 42, 65, 95, 136, 212, 308, 444, 687, 1005, 1439, 2242, 3257, 4696, 7266, 10629, 15219

Offset: 0

N. J. A. Sloane, Aug 07 2012

The initial terms roughly satisfy a(n) approx.= a(n-1)+a(n-3), which leads to the guess that perhaps a(n) ~ 1.4655^n, from the real zero of x^3-x-1. - N. J. A. Sloane, Aug 08 2012

			The values of A215244(k) for k=8 through 15 are (4, 3, 3, 3, 4, 3, 4, 8), with minimal value a(3) = 3.

Giovanni Resta, Examples of words attaining the minimal value for n = 0..25

Cf. A215244, A215246, A215253, A215254. A215255 gives an upper bound.

A215245 := proc(n)
    local a,k ;
    a := A215244(2^n) ;
    for k from 2^n+1 to 2^(n+1)-1 do
        a := min(a,A215244(k)) ;
    end do:
    a ;
end proc: # R. J. Mathar, Aug 07 2012

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];
a215244[n_] := If[n == 1, 1, b[IntegerDigits[n, 2]]];
a215245[n_] := Module[{a, k}, a = a215244[2^n]; For[k = 2^n+1, k <= 2^(n+1) - 1, k++, a = Min[a, a215244[k]]]; a];
a215245 /@ Range[0, 20] (* Jean-François Alcover, Oct 28 2019 *)

a(10)-a(13) from R. J. Mathar, Aug 07 2012
a(14)-a(17) from N. J. A. Sloane, Aug 08 2012, using Mathar's Maple code.
a(18)-a(25) from Giovanni Resta, Mar 19 2013

A215254 Consider numbers m in the range 2^n <= m < 2^(n+1); the smallest A215244(m) in this range is k=A215245(n); a(n) = binary representation of m for the first time this k appears.

Original entry on oeis.org

1, 10, 100, 1001, 10010, 100101, 1001101, 10010110, 101001101, 1001011001, 10010110010, 100101100101, 1001101001101, 10010110010110, 101001101001101, 1001011001011001, 10010110010110010, 100101100101100101

Offset: 0

N. J. A. Sloane, Aug 14 2012

a(n) is an example, the first that is encountered, of a binary vector of length n that has the smallest number of factorizations as a product of palindromes.

			If the numbers are written under each other, there is a suggestion of a pattern (see A215255 for the most obvious pattern). It would be interesting to have more terms to see if the pattern continues.
   0  1                            1
   1  10                           10
   2  100                          100
   3  1001                         1001
   4  10010                        10010
   5  100101                       a
   6  1001101                      b1
   7  10010110                     a10
   8  101001101                    10b1
   9  1001011001                   a1001
  10  10010110010                  a10010
  11  100101100101                 aa
  12  1001101001101                bb1
  13  10010110010110               aa10
  14  101001101001101              10bb1
  15  1001011001011001             aa1001
  16  10010110010110010            aa10010
  17  100101100101100101           aaa
  18  1001101001101001101          bbb1
  19  10010110010110010110         aaa10
  20  101001101001101001101        10bbb1
  21  1001011001011001011001       aaa1001
  22  10010110010110010110010      aaa10010
  23  100101100101100101100101     aaaa
  24  1001101001101001101001101    bbbb1
  25  10010110010110010110010110   aaaa10
  26  101001101001101001101001101  10bbbb1
The rightmost column is obtained by substituting a=100101 and b=100110. A period of 6 is apparent. - _Lars Blomberg_, May 18 2019

Lars Blomberg, Table of n, a(n) for n = 0..26

Cf. A215244, A215245, A215246, A215253, A215255.

Example augmented by Lars Blomberg, May 18 2019

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

A215246 a(n) = maximal value of k such that A215244(k) = n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A215245 a(n) = minimal value of A215244(k) for 2^n <= k < 2^(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A215254 Consider numbers m in the range 2^n <= m < 2^(n+1); the smallest A215244(m) in this range is k=A215245(n); a(n) = binary representation of m for the first time this k appears.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions