cp's OEIS Frontend

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

%I A023894 #30 Jul 16 2024 12:41:19
%S A023894 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 A023894 196,231,275,322,380,443,520,607,705,819,950,1099,1268,1461,1681,1932,
%U A023894 2214,2533,2898,3305,3768,4285,4872,5530,6267,7094,8022,9060
%N A023894 Number of partitions of n into prime power parts (1 excluded).
%H A023894 Seiichi Manyama, <a href="/A023894/b023894.txt">Table of n, a(n) for n = 0..10000</a>
%H A023894 E. Grosswald, <a href="http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.mmj/1028998381">Partitions into prime powers</a>
%F A023894 G.f.: Prod(p prime, Prod(k >= 1, 1/(1-x^(p^k))))
%e A023894 From _Gus Wiseman_, Jul 28 2022: (Start)
%e A023894 The a(0) = 1 through a(9) = 7 partitions:
%e A023894   ()  .  (2)  (3)  (4)   (5)   (33)   (7)    (8)     (9)
%e A023894                    (22)  (32)  (42)   (43)   (44)    (54)
%e A023894                                (222)  (52)   (53)    (72)
%e A023894                                       (322)  (332)   (333)
%e A023894                                              (422)   (432)
%e A023894                                              (2222)  (522)
%e A023894                                                      (3222)
%e A023894 (End)
%t A023894 Table[Length[Select[IntegerPartitions[n],And@@PrimePowerQ/@#&]],{n,0,30}] (* _Gus Wiseman_, Jul 28 2022 *)
%o A023894 (PARI) is_primepower(n)= {ispower(n, , &n); isprime(n)}
%o A023894 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 A023894 \\ _Michel Marcus_, Mar 09 2013
%o A023894 (Python)
%o A023894 from functools import lru_cache
%o A023894 from sympy import factorint
%o A023894 @lru_cache(maxsize=None)
%o A023894 def A023894(n):
%o A023894     @lru_cache(maxsize=None)
%o A023894     def c(n): return sum((p**(e+1)-p)//(p-1) for p,e in factorint(n).items())
%o A023894     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 A023894 The multiplicative version (factorizations) is A000688, coprime A354911.
%Y A023894 Allowing 1's gives A023893, strict A106244, ranked by A302492.
%Y A023894 The strict version is A054685.
%Y A023894 The version for just primes is ranked by A076610, squarefree A356065.
%Y A023894 Twice-partitions of this type are counted by A279784, factorizations A295935.
%Y A023894 These partitions are ranked by A355743.
%Y A023894 A000041 counts partitions, strict A000009.
%Y A023894 A001222 counts prime-power divisors.
%Y A023894 A072233 counts partitions by sum and length.
%Y A023894 A246655 lists the prime-powers (A000961 includes 1), towers A164336.
%Y A023894 Cf. A001970, A055887, A063834, A085970.
%K A023894 nonn
%O A023894 0,5
%A A023894 _Olivier Gérard_