%I #55 Jul 15 2024 15:33:23
%S 1,1,2,3,5,7,10,14,20,27,36,48,63,82,105,134,171,215,269,335,415,511,
%T 626,764,929,1125,1356,1631,1953,2333,2776,3296,3903,4608,5427,6377,
%U 7476,8744,10205,11886,13818,16032,18565,21463,24768,28536
%N Number of partitions of n into prime power parts (1 included); number of nonisomorphic Abelian subgroups of symmetric group S_n.
%H Seiichi Manyama, <a href="/A023893/b023893.txt">Table of n, a(n) for n = 0..10000</a>
%H <a href="/index/Gre#groups">Index entries for sequences related to groups</a>
%F G.f.: (Product_{p prime} Product_{k>=1} 1/(1-x^(p^k))) / (1-x).
%e From _Gus Wiseman_, Jul 28 2022: (Start)
%e The a(0) = 1 through a(6) = 10 partitions:
%e () (1) (2) (3) (4) (5) (33)
%e (11) (21) (22) (32) (42)
%e (111) (31) (41) (51)
%e (211) (221) (222)
%e (1111) (311) (321)
%e (2111) (411)
%e (11111) (2211)
%e (3111)
%e (21111)
%e (111111)
%e (End)
%t Table[Length[Select[IntegerPartitions[n],Count[Map[Length,FactorInteger[#]], 1] == Length[#] &]], {n, 0, 35}] (* _Geoffrey Critzer_, Oct 25 2015 *)
%t nmax = 50; Clear[P]; P[m_] := P[m] = Product[Product[1/(1-x^(p^k)), {k, 1, m}], {p, Prime[Range[PrimePi[nmax]]]}]/(1-x)+O[x]^nmax // CoefficientList[ #, x]&; P[1]; P[m=2]; While[P[m] != P[m-1], m++]; P[m] (* _Jean-François Alcover_, Aug 31 2016 *)
%o (PARI) lista(m) = {x = t + t*O(t^m); gf = prod(k=1, m, if (isprimepower(k), 1/(1-x^k), 1))/(1-x); for (n=0, m, print1(polcoeff(gf, n, t), ", "));} \\ _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 A023893(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())+1
%o return (c(n)+sum(c(k)*A023893(n-k) for k in range(1,n)))//n if n else 1 # _Chai Wah Wu_, Jul 15 2024
%Y Cf. A009490, A023894 (first differences), A062297 (number of Abelian subgroups).
%Y Cf. A018819, A062051, A131995.
%Y The multiplicative version (factorizations) is A000688.
%Y Not allowing 1's gives A023894, strict A054685, ranked by A355743.
%Y The version for just primes (not prime-powers) is A034891, strict A036497.
%Y The strict version is A106244.
%Y These partitions are ranked by A302492.
%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, A279784, A295935, A356065.
%K nonn
%O 0,3
%A _Olivier Gérard_