OFFSET
0,7
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..10000 (1000 terms from T. D. Noe)
Noah Lebowitz-Lockard and Joseph Vandehey, On the number of partitions of a number into distinct divisors, arXiv:2402.08119 [math.NT], 2024. See p. 2.
FORMULA
a(n) = A065205(n) + 1.
a(n) = f(n, n, 1) with f(n, m, k) = if k <= m then f(n, m, k + 1) + f(n, m - k, k + 1)*0^(n mod k) else 0^m. - Reinhard Zumkeller, Dec 11 2009
a(n) = [x^n] Product_{d|n} (1 + x^d). - Ilya Gutkovskiy, Jul 26 2017
a(n) = 1 if n is deficient (A005100) or weird (A006037). a(n) = 2 if n is perfect (A000396). - Alonso del Arte, Sep 24 2017
EXAMPLE
a(12) = 3 because we have the partitions [12], [6, 4, 2], and [6, 3, 2, 1].
MAPLE
with(numtheory): a:=proc(n) local div, g, gser: div:=divisors(n): g:=product(1+x^div[j], j=1..tau(n)): gser:=series(g, x=0, 105): coeff(gser, x^n): end: seq(a(n), n=1..100); # Emeric Deutsch, Mar 30 2006
# Alternative:
with(numtheory):
a:= proc(n) local b, l; l:= sort([(divisors(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-1))))
end; forget(b):
b(n, nops(l))
end:
seq(a(n), n=0..100); # Alois P. Heinz, Feb 05 2014
MATHEMATICA
A033630 = Table[SeriesCoefficient[Series[Times@@((1 + z^#) & /@ Divisors[n]), {z, 0, n}], n ], {n, 512}] (* Wouter Meeussen *)
A033630[n_] := f[n, n, 1]; f[n_, m_, k_] := f[n, m, k] = If[k <= m, f[n, m, k + 1] + f[n, m - k, k + 1] * Boole[Mod[n, k] == 0], Boole[m == 0]]; Array[A033630, 101, 0] (* Jean-François Alcover, Jul 29 2015, after Reinhard Zumkeller *)
PROG
(Haskell)
a033630 0 = 1
a033630 n = p (a027750_row n) n where
p _ 0 = 1
p [] _ = 0
p (d:ds) m = if d > m then 0 else p ds (m - d) + p ds m
-- Reinhard Zumkeller, Feb 23 2014, Apr 04 2012, Oct 27 2011
(SageMath)
def A033630(n: int) -> int:
if n == 0: return 1
divs = divisors(n)
dp = [0] * (n + 1)
dp[0] = 1
for d in divs:
for j in range(n, d - 1, -1):
dp[j] += dp[j - d]
return dp[n]
print([A033630(n) for n in range(101)]) # Peter Luschny, Nov 24 2025
(Python)
from functools import lru_cache
from sympy import divisors
def A033630(n):
ds = divisors(n)+[n+1]
@lru_cache(maxsize=None)
def f(m, k): return int(not m) if ds[k]>m else f(m, k+1)+f(m-ds[k], k+1)
return f(n, 0) # Chai Wah Wu, Mar 03 2026
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
More terms from Reinhard Zumkeller, Apr 21 2003
STATUS
approved