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

Author

Olivier Gérard

Keywords

• nonn

Examples

			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)
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..10000
• E. Grosswald, Partitions into prime powers

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.

Programs

Mathematica

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

PARI

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

Python

from functools import lru_cache
from sympy import factorint
@lru_cache(maxsize=None)
def A023894(n):
    @lru_cache(maxsize=None)
    def c(n): return sum((p**(e+1)-p)//(p-1) for p,e in factorint(n).items())
    return (c(n)+sum(c(k)*A023894(n-k) for k in range(1,n)))//n if n else 1 # Chai Wah Wu, Jul 15 2024

Formula

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