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

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

Offset: 0

Author

Naohiro Nomoto, Jan 26 2002

Keywords

• easy
• nonn
• look

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A018818, A014652.

Main diagonal of A107329 (for n>=1).

Programs

Maple

with(numtheory):
a:= proc(n) local b, l; l:= sort([factorset(n)[]]):
      b:= proc(m, i) option remember; `if`(m=0, 1, `if`(i<1, 0,
             b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i))))
          end; forget(b):
      b(n, nops(l))
    end:
seq(a(n), n=0..100); # Alois P. Heinz, Feb 05 2014

Mathematica

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 *)

Python

from sympy import factorint
from functools import cache
def A066882(n):
    @cache
    def b(m, i):
        if m == 0: return 1
        if i < 0: return 0
        return b(m, i-1) + (0 if l[i]>m else b(m-l[i], i))
    l = sorted(factorint(n))
    return b(n, len(l)-1)
print([A066882(n) for n in range(99)]) # Michael S. Branicky, Jan 08 2025 after Alois P. Heinz

Formula

Coefficient of x^n in expansion of 1/Product_{d is prime divisor of n} (1-x^d). - Vladeta Jovovic, Apr 11 2004

Extensions

More terms from Sascha Kurz, Mar 23 2002

Corrected by Vladeta Jovovic, Apr 11 2004