A145513 -id:A145513 - cp's OEIS frontend

A002577 Number of partitions of 2^n into powers of 2.

1, 2, 4, 10, 36, 202, 1828, 27338, 692004, 30251722, 2320518948, 316359580362, 77477180493604, 34394869942983370, 27893897106768940836, 41603705003444309596874, 114788185359199234852802340, 588880400923055731115178072778, 5642645813427132737155703265972004

Offset: 0

N. J. A. Sloane

For given m, the general formula for t_m(n, k) and the corresponding tables T, computed as in the example, determine a family of related sequences (placed in the rows or in the columns of T). For example, the numbers from the second row of T, computed for given m and n > 2, are the (m+2)-gonal numbers. So the second row contains the first members of: A000290 (the square numbers) when m=2, A000326 (the pentagonal numbers) when m=3, and so on. But rows IV, V etc. of the given table are not represented in the OEIS till now. - Valentin Bakoev, Feb 25 2009; edited by M. F. Hasler, Feb 09 2014

			To compute t_2(6,1) we can use a table T, defined as T[i,j]= t_2(i,j), for i=1,2,...,6(=n), and j= 0,1,2,...,32(= k*m^{n-1}). It is: 1,2,3,4,5,6,7,8,9...,33; 1,4,9,16,25,36,49...,81; (so the second row contains the first members of A000290 -- the square numbers) 1,10,35,84,165,...,969; (so the third row contains the first members of A000447. The r-th tetrahedral number is given by formula r(r+1)(r+2)/6. This row (also A000447) contains the tetrahedral numbers, obtained for r=1,3,5,7,...) 1,36,201,656,1625; 1,202,1827; 1,1828; Column 1 contains the first 6 members of A002577. - _Valentin Bakoev_, Feb 25 2009
G.f. = 1 + 2*x + 4*x^2 + 10*x^3 + 36*x^4 + 202*x^5 + 1828*x^6 + ...

R. F. Churchhouse, Binary partitions, pp. 397-400 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
Lawrence, Jim. "Dual-Antiprisms and Partitions of Powers of 2 into Powers of 2." Discrete & Computational Geometry, Vol. 16 (2019): 465-478. See page 466.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..85
V. Bakoev, Algorithmic approach to counting of certain types m-ary partitions, Discrete Mathematics, 275 (2004) pp.17-41.
C. Banderier, H.-K. Hwang, V. Ravelomanana and V. Zacharovas, Analysis of an exhaustive search algorithm in random graphs and the n^{c logn}-asymptotics, 2012. - From _N. J. A. Sloane_, Dec 23 2012
G. Blom and C.-E. Froeberg, Om myntvaexling, (On money-changing) [ Swedish ], Nordisk Matematisk Tidskrift, 10 (1962), 55-69, 103.
G. Blom and C.-E. Froeberg, Om myntvaexling (On money-changing) [Swedish], Nordisk Matematisk Tidskrift, 10 (1962), 55-69, 103. [Annotated scanned copy]
R. F. Churchhouse, Congruence properties of the binary partition function, Math. Proc. Cambr. Phil. Soc. vol 66, no. 2 (1969), 365-370.
Carl-Erik Froberg, Accurate estimation of the number of binary partitions, BIT Numerical Mathematics vol. 17, no 4 (1977) 386-391.
C.-E. Froberg, Accurate estimation of the number of binary partitions [Annotated scanned copy]
H. Minc, The free commutative entropic logarithmetic, Proc. Roy. Soc. Edinburgh Sect. A 65 1959 177-192 (1959).

a(n) = A000123(2^(n-1)) = A018818(2^n).
Cf. A078537, A078121, A000290, A000447.
Column k=2 of A145515, diagonal of A152977. - Alois P. Heinz, Mar 25 2012
See also A002575, A002576.
A column of A125790.
Cf. A000079, A078125, A145513.

import Data.MemoCombinators (memo2, list, integral)
a002577 n = a002577_list !! n
a002577_list = f [1] where
   f xs = (p' xs $ last xs) : f (1 : map (* 2) xs)
   p' = memo2 (list integral) integral p
   p  0 = 1; p []  = 0
   p ks'@(k:ks) m = if m < k then 0 else p' ks' (m - k) + p' ks m
-- Reinhard Zumkeller, Nov 27 2015

A002577 := proc(n) if n<=1 then n+1 else A000123(2^(n-1)); fi; end;

$RecursionLimit = 10^5; (* b = A000123 *) b[0] = 1; b[n_?EvenQ] := b[n] = b[n-1] + b[n/2]; b[n_?OddQ] := b[n] = b[n-1] + b[(n-1)/2]; a[n_] := b[2^(n-1)]; a[0] = 1; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Nov 23 2011 *)
a[ n_] := SeriesCoefficient[ 1 / Product[ 1 - x^2^k, {k, 0, n}], {x, 0, 2^n}]; (* Michael Somos, Apr 21 2014 *)

a(n)=polcoeff(prod(j=0,n,1/(1-x^(2^j)+x*O(x^(2^n)))),2^n) \\ Paul D. Hanna

a(n) is about 0.9233*Sum_j {i=0, 1, 2, 3, ...} 2^(j*(2n-j-1)/2)/j!. - Henry Bottomley, Jul 23 2003
a(n) = A078121(n+1, 1). - Paul D. Hanna, Sep 13 2004
A002577(n)-1 = A125792(n). - Let m > 1, n > 0 and k >= 0. The general formula for the number of all partitions of k*m^n into powers of m is t_m(n, k)= k+1 if n=1, t_m(n, k)= 1 if k=0, and t_m(n, k)= t_m(n, k-1) + t_m(n-1, k*m) if n > 1 and k > 0. A002577 is obtained for m=2 and n=1,2,3,... - Valentin Bakoev, Feb 25 2009
a(n) = [x^(2^n)] 1/Product_{j>=0} (1-x^(2^j)). - Alois P. Heinz, Sep 27 2011

Edited by M. F. Hasler, Feb 09 2014

A145515 Square array A(n,k), n>=0, k>=0, read by antidiagonals: A(n,k) is the number of partitions of k^n into powers of k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 4, 1, 1, 1, 2, 5, 10, 1, 1, 1, 2, 6, 23, 36, 1, 1, 1, 2, 7, 46, 239, 202, 1, 1, 1, 2, 8, 82, 1086, 5828, 1828, 1, 1, 1, 2, 9, 134, 3707, 79326, 342383, 27338, 1, 1, 1, 2, 10, 205, 10340, 642457, 18583582, 50110484, 692004, 1, 1, 1, 2, 11, 298, 24901, 3649346, 446020582, 14481808030, 18757984046, 30251722, 1, 1

Offset: 0

Alois P. Heinz, Oct 11 2008

			A(2,3) = 5, because there are 5 partitions of 3^2=9 into powers of 3: [1,1,1,1,1,1,1,1,1], [1,1,1,1,1,1,3], [1,1,1,3,3], [3,3,3], [9].
Square array A(n,k) begins:
  1,  1,   1,    1,     1,      1,  ...
  1,  1,   2,    2,     2,      2,  ...
  1,  1,   4,    5,     6,      7,  ...
  1,  1,  10,   23,    46,     82,  ...
  1,  1,  36,  239,  1086,   3707,  ...
  1,  1, 202, 5828, 79326, 642457,  ...

Alois P. Heinz, Antidiagonals n = 0..40, flattened

Columns k=0+1, 2-10 give: A000012, A002577, A078125, A078537, A111822, A111827, A111832, A111837, A145512, A145513.
Row n=3 gives: A189890(k+1).
Main diagonal gives: A145514.
Cf. A007318.

b:= proc(n, j, k) local nn;
      nn:= n+1;
      if n<0  then 0
    elif j=0  or n=0 or k<=1 then 1
    elif j=1  then nn
    elif n>=j then (nn-j) *binomial(nn, j) *add(binomial(j, h)
                   /(nn-j+h) *b(j-h-1, j, k) *(-1)^h, h=0..j-1)
              else b(n, j, k):= b(n-1, j, k) +b(k*n, j-1, k)
      fi
    end:
A:= (n, k)-> b(1, n, k):
seq(seq(A(n, d-n), n=0..d), d=0..13);

b[n_, j_, k_] := Module[{nn = n+1}, Which[n < 0, 0, j == 0 || n == 0 || k <= 1, 1, j == 1, nn, n >= j, (nn-j)*Binomial[nn, j]*Sum[Binomial[j, h]/(nn-j+h)* b[j-h-1, j, k]*(-1)^h, {h, 0, j-1}], True, b[n, j, k] = b[n-1, j, k] + b[k*n, j-1, k] ] ]; a[n_, k_] := b[1, n, k]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 13}] // Flatten (* Jean-François Alcover, Dec 12 2013, translated from Maple *)

See program.

For k>1: A(n,k) = [x^(k^n)] 1/Product_{j>=0} (1-x^(k^j)).

Edited by Alois P. Heinz, Jan 12 2011

A078125 Number of partitions of 3^n into powers of 3.

Original entry on oeis.org

1, 2, 5, 23, 239, 5828, 342383, 50110484, 18757984046, 18318289003448, 47398244089264547, 329030840161393127681, 6190927493941741957366100, 318447442589056401640929570896, 45106654667152833836835578059359839

Offset: 0

Paul D. Hanna, Nov 18 2002

nonn

a(n) = sum of the n-th row of lower triangular matrix of A078122.
From Valentin Bakoev, Feb 22 2009: (Start)
a(n) = the partitions of 3^n into powers of 3.
A125801(n) = a(n+1) - 1.
For given m, the general formula for t_m(n, k) and the corresponding tables T, computed as in the example, determine a family of related sequences (placed in the rows or in the columns of T). For example, the sequences from the 3rd, 4th, etc. rows of the given table are not represented in the OEIS till now. (End)

			Square of A078122 = A078123 as can be seen by 4 X 4 submatrix:
[1,_0,_0,0]^2=[_1,_0,_0,_0]
[1,_1,_0,0]___[_2,_1,_0,_0]
[1,_3,_1,0]___[_5,_6,_1,_0]
[1,12,_9,1]___[23,51,18,_1]
To obtain t_3(5,2) we use the table T, defined as T[i,j]= t_3(i,j), for i=1,2,...,5(=n), and j= 0,1,2,...,162(= k.m^{n-1}). It is: 1,2,3,4,5,6,7,8,...,162; 1,5,12,22,35,51,...,4510; (this row contains the first 55 members of A000326 - the pentagonal numbers) 1,23,93,238,485,...,29773; 1,239,1632,5827,15200,32856,62629; 1,5828,68457; Column 1 contains the first 5 members of this sequence. - _Valentin Bakoev_, Feb 22 2009

Alois P. Heinz, Table of n, a(n) for n = 0..40
V. Bakoev, Algorithmic approach to counting of certain types m-ary partitions, Discrete Mathematics, 275 (2004) pp. 17-41.

Cf. A078121, A078122 (matrix shift when cubed), A078123, A078124, A125801.
Column k=3 of A145515. - Alois P. Heinz, Sep 27 2011
Cf. A000244, A002577, A145513.

import Data.MemoCombinators (memo2, list, integral)
a078125 n = a078125_list !! n
a078125_list = f [1] where
   f xs = (p' xs $ last xs) : f (1 : map (* 3) xs)
   p' = memo2 (list integral) integral p
   p  0 = 1; p []  = 0
   p ks'@(k:ks) m = if m < k then 0 else p' ks' (m - k) + p' ks m
-- Reinhard Zumkeller, Nov 27 2015

m[i_, j_] := m[i, j]=If[j==0||i==j, 1, m3[i-1, j-1]]; m2[i_, j_] := m2[i, j]=Sum[m[i, k]m[k, j], {k, j, i}]; m3[i_, j_] := m3[i, j]=Sum[m[i, k]m2[k, j], {k, j, i}]; a[n_] := m2[n, 0]

Denote the sum m^n + m^n + ... + m^n, k times, by k*m^n (m > 1, n > 0 and k are natural numbers). The general formula for the number of all partitions of the sum k*m^n into powers of m is t_m(n, k)= k+1 if n=1, t_m(n, k)= 1 if k=0, and t_m(n, k)= t_m(n, k-1) + t_m(n-1, k*m) if n > 1 and k > 0. a(n) is obtained for m=3 and n=1,2,3,... - Valentin Bakoev, Feb 22 2009

a(n) = [x^(3^n)] 1/Product_{j>=0} (1-x^(3^j)). - Alois P. Heinz, Sep 27 2011

A179051 Number of partitions of n into powers of 10 (cf. A011557).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10

Offset: 0

Reinhard Zumkeller, Jun 27 2010

nonn

A179052 and A008592 give record values and where they occur.

			a(19) = #{10 + 9x1, 19x1} = 2;
a(20) = #{10 + 10, 10 + 10x1, 20x1} = 3;
a(21) = #{10 + 10 + 1, 10 + 11x1, 21x1} = 3.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Index entries for related partition-counting sequences

Number of partitions of n into powers of b: A018819 (b=2), A062051 (b=3).
Cf. A206245, A000041, A179051.
Cf. A133880, A132272.
Cf. A008592, A179052.

a179051 = p 1 where
   p _ 0 = 1
   p k m = if m < k then 0 else p k (m - k) + p (k * 10) m
-- Reinhard Zumkeller, Feb 05 2012

terms = 10001;
CoefficientList[Product[1/(1 - x^(10^k)) + O[x]^terms,
     {k, 0, Log[10, terms] // Ceiling}], x]
(* Jean-François Alcover, Dec 12 2021, after Ilya Gutkovskiy *)

a(n) = A133880(n) for n < 90; a(n) = A132272(n) for n < 100.
a(10^n) = A145513(n).
a(10*n) = A179052(n).
A179052(n) = a(A008592(n));
a(n) = p(n,1) where p(n,k) = if k<=n then p(10*[(n-k)/10],k)+p(n,10*k) else 0^n.
G.f.: Product_{k>=0} 1/(1 - x^(10^k)). - Ilya Gutkovskiy, Jul 26 2017

cp's OEIS Frontend

A002577 Number of partitions of 2^n into powers of 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A145515 Square array A(n,k), n>=0, k>=0, read by antidiagonals: A(n,k) is the number of partitions of k^n into powers of k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A078125 Number of partitions of 3^n into powers of 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A179051 Number of partitions of n into powers of 10 (cf. A011557).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A179052 Range and record values of number of partitions of n into powers of 10 (cf. A179051).

Views

Author

Keywords

Comments

Links