cp's OEIS Frontend

A066882 Number of partitions of n into prime divisors of n.

%I A066882 #24 Jan 08 2025 08:32:57
%S A066882 1,0,1,1,1,1,2,1,1,1,2,1,3,1,2,2,1,1,4,1,3,2,2,1,5,1,2,1,3,1,21,1,1,2,
%T A066882 2,2,7,1,2,2,5,1,28,1,3,4,2,1,9,1,6,2,3,1,10,2,5,2,2,1,71,1,2,4,1,2,
%U A066882 42,1,3,2,43,1,13,1,2,6,3,2,49,1,9,1,2,1,97,2,2,2,5,1,151,2,3,2,2,2,17,1,8
%N A066882 Number of partitions of n into prime divisors of n.
%H A066882 Alois P. Heinz, <a href="/A066882/b066882.txt">Table of n, a(n) for n = 0..10000</a>
%F A066882 Coefficient of x^n in expansion of 1/Product_{d is prime divisor of n} (1-x^d). - _Vladeta Jovovic_, Apr 11 2004
%p A066882 with(numtheory):
%p A066882 a:= proc(n) local b, l; l:= sort([factorset(n)[]]):
%p A066882       b:= proc(m, i) option remember; `if`(m=0, 1, `if`(i<1, 0,
%p A066882              b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i))))
%p A066882           end; forget(b):
%p A066882       b(n, nops(l))
%p A066882     end:
%p A066882 seq(a(n), n=0..100); # _Alois P. Heinz_, Feb 05 2014
%t A066882 a[0] = 1; a[n_] := SeriesCoefficient[1/Product[1-x^d, {d, FactorInteger[n][[All, 1]]}], {x, 0, n}]; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Jul 30 2015, after _Vladeta Jovovic_ *)
%o A066882 (Python)
%o A066882 from sympy import factorint
%o A066882 from functools import cache
%o A066882 def A066882(n):
%o A066882     @cache
%o A066882     def b(m, i):
%o A066882         if m == 0: return 1
%o A066882         if i < 0: return 0
%o A066882         return b(m, i-1) + (0 if l[i]>m else b(m-l[i], i))
%o A066882     l = sorted(factorint(n))
%o A066882     return b(n, len(l)-1)
%o A066882 print([A066882(n) for n in range(99)]) # _Michael S. Branicky_, Jan 08 2025 after _Alois P. Heinz_
%Y A066882 Cf. A018818, A014652.
%Y A066882 Main diagonal of A107329 (for n>=1).
%K A066882 easy,nonn,look
%O A066882 0,7
%A A066882 _Naohiro Nomoto_, Jan 26 2002
%E A066882 More terms from _Sascha Kurz_, Mar 23 2002
%E A066882 Corrected by _Vladeta Jovovic_, Apr 11 2004