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

%I #30 Jul 16 2024 12:41:19

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

%T 196,231,275,322,380,443,520,607,705,819,950,1099,1268,1461,1681,1932,

%U 2214,2533,2898,3305,3768,4285,4872,5530,6267,7094,8022,9060

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

%H Seiichi Manyama, <a href="/A023894/b023894.txt">Table of n, a(n) for n = 0..10000</a>

%H E. Grosswald, <a href="http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.mmj/1028998381">Partitions into prime powers</a>

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

%e From _Gus Wiseman_, Jul 28 2022: (Start)

%e The a(0) = 1 through a(9) = 7 partitions:

%e () . (2) (3) (4) (5) (33) (7) (8) (9)

%e (22) (32) (42) (43) (44) (54)

%e (222) (52) (53) (72)

%e (322) (332) (333)

%e (422) (432)

%e (2222) (522)

%e (3222)

%e (End)

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

%o (PARI) is_primepower(n)= {ispower(n, , &n); isprime(n)}

%o 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), ", "));}

%o \\ _Michel Marcus_, Mar 09 2013

%o (Python)

%o from functools import lru_cache

%o from sympy import factorint

%o @lru_cache(maxsize=None)

%o def A023894(n):

%o @lru_cache(maxsize=None)

%o def c(n): return sum((p**(e+1)-p)//(p-1) for p,e in factorint(n).items())

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

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

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

%Y The strict version is A054685.

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

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

%Y These partitions are ranked by A355743.

%Y A000041 counts partitions, strict A000009.

%Y A001222 counts prime-power divisors.

%Y A072233 counts partitions by sum and length.

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

%Y Cf. A001970, A055887, A063834, A085970.

%K nonn

%O 0,5

%A _Olivier GĂ©rard_