A023894 Number of partitions of n into prime power parts (1 excluded).

1, 0, 1, 1, 2, 2, 3, 4, 6, 7, 9, 12, 15, 19, 23, 29, 37, 44, 54, 66, 80, 96, 115, 138, 165, 196, 231, 275, 322, 380, 443, 520, 607, 705, 819, 950, 1099, 1268, 1461, 1681, 1932, 2214, 2533, 2898, 3305, 3768, 4285, 4872, 5530, 6267, 7094, 8022, 9060

Offset

0,5

Links

Seiichi Manyama, Table of n, a(n) for n = 0..10000

E. Grosswald, Partitions into prime powers

Formula

G.f.: Prod(p prime, Prod(k >= 1, 1/(1-x^(p^k))))

Example

From Gus Wiseman, Jul 28 2022: (Start)
The a(0) = 1 through a(9) = 7 partitions:
  ()  .  (2)  (3)  (4)   (5)   (33)   (7)    (8)     (9)
                   (22)  (32)  (42)   (43)   (44)    (54)
                               (222)  (52)   (53)    (72)
                                      (322)  (332)   (333)
                                             (422)   (432)
                                             (2222)  (522)
                                                     (3222)
(End)

Mathematica

Table[Length[Select[IntegerPartitions[n], And@@PrimePowerQ/@#&]], {n, 0, 30}] (* Gus Wiseman, Jul 28 2022 *)

Prog

(PARI) isprimepower(n)= {ispower(n, , &n); isprime(n)}
lista(m) = {x = t + t*O(t^m); gf = prod(k=1, m, if (isprimepower(k), 1/(1-x^k), 1)); for (n=0, m, print1(polcoeff(gf, n, t), ", ")); }
\\ Michel Marcus, Mar 09 2013

Crossrefs

The multiplicative version (factorizations) is A000688, coprime A354911.

Allowing 1's gives A023893, strict A106244, ranked by A302492.

The strict version is A054685.

The version for just primes is ranked by A076610, squarefree A356065.

Twice-partitions of this type are counted by A279784, factorizations A295935.

These partitions are ranked by A355743.

A000041 counts partitions, strict A000009.

A001222 counts prime-power divisors.

A072233 counts partitions by sum and length.

A246655 lists the prime-powers (A000961 includes 1), towers A164336.

Cf. A001970, A055887, A063834, A085970.

Sequence in context: A246762 A093950 A280715 * A285799 A241772 A323053

Adjacent sequences: A023891 A023892 A023893 * A023895 A023896 A023897

Keyword

nonn

Author

Olivier Gérard

Status

approved