A033630 Number of partitions of n into distinct divisors of n.

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 1, 6, 1, 1, 1, 2, 1, 4, 1, 1, 1, 1, 1, 8, 1, 1, 1, 4, 1, 3, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 4, 1, 3, 1, 1, 1, 35, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 32, 1, 1, 1, 1, 1, 2, 1, 7, 1, 1, 1, 26, 1, 1, 1, 2, 1, 24, 1, 1, 1, 1, 1, 22, 1, 1, 1, 3

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(A005100(n)) = 1; a(A005835(n)) > 1. - Reinhard Zumkeller, Mar 02 2007

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
# second Maple program:
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

Crossrefs

Cf. A018818, A065205.

Cf. A083206. - Reinhard Zumkeller, Jul 19 2010

Cf. A000009, A005153.

Cf. A211111, A027750.

Cf. A225245.

Cf. A000396, A005100, A005835, A006037.

Sequence in context: A328457 A340827 A360119 * A308608 A371213 A323719

Adjacent sequences: A033627 A033628 A033629 * A033631 A033632 A033633

Keyword

nonn

Author

Marc LeBrun

Extensions

More terms from Reinhard Zumkeller, Apr 21 2003

Status

approved