A018818 Number of partitions of n into divisors of n.

1, 2, 2, 4, 2, 8, 2, 10, 5, 11, 2, 45, 2, 14, 14, 36, 2, 81, 2, 92, 18, 20, 2, 458, 7, 23, 23, 156, 2, 742, 2, 202, 26, 29, 26, 2234, 2, 32, 30, 1370, 2, 1654, 2, 337, 286, 38, 2, 9676, 9, 407, 38, 454, 2, 3132, 38, 3065, 42, 47, 2, 73155, 2, 50, 493, 1828, 44, 5257, 2, 740, 50, 5066

Offset: 1

Author

David W. Wilson

Keywords

• nonn
• nice
• look

Comments

From Reinhard Zumkeller, Dec 11 2009: (Start)

For odd primes p: a(p^2) = p + 2; for n > 1: a(A001248(n)) = A052147(n);

For odd primes p > 3, a(3*p) = 2*p + 4; for n > 2: a(A001748(n)) = A100484(n) + 4. (End)

From Matthew Crawford, Jan 19 2021: (Start)

For a prime p, a(p^3) = (p^3 + p^2 + 2*p + 4)/2;

For distinct primes p and q, a(p*q) = (p+1)*(q+1)/2 + 2. (End)

Examples

			The a(6) = 8 representations of 6 are 6 = 3 + 3 = 3 + 2 + 1 = 3 + 1 + 1 + 1 = 2 + 2 + 2 = 2 + 2 + 1 + 1 = 2 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 + 1.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
• Douglas Bowman et al., Problem 6640: Partitions of n into parts which are divisors of n, American Mathematical Monthly, 99(3) (1992), 276-277.
• Hansraj Gupta, Partitions of n into divisors of m, Indian J. Pure Appl. Math., 6(11) (1975), 1276-1286.
• Hansraj Gupta, Partitions of n into divisors of m, Indian J. Pure Appl. Math., 6(11) (1975), 1276-1286.
• Martin Klazar, What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I, arXiv:1808.08449 [math.CO], 2018.
• 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. 1.
• Rémy Sigrist, Colored logarithmic scatterplot of the first 10000 terms (where the color is function of A000005(n)).
• Index entries for sequences related to partitions.

Crossrefs

Cf. A002577, A027750, A033630, A072721, A161148 (partitions in squared divisors), A171565, A210442, A211110, A225244, A306387, A379957.

Cf. A000005, A001248, A001748, A052147, A100484.

Programs

Haskell

a018818 n = p (init $ a027750_row n) n + 1 where
   p _      0 = 1
   p []     _ = 0
   p ks'@(k:ks) m | m < k     = 0
                  | otherwise = p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Apr 02 2012

Magma

[#RestrictedPartitions(n,{d:d in Divisors(n)}): n in [1..100]]; // Marius A. Burtea, Jan 02 2019

Maple

A018818 := proc(n)
    local a,p,w,el ;
    a := 0 ;
    for p in combinat[partition](n) do
        w := true ;
        for el in p do
            if modp(n,el) <> 0 then
                w := false;
                break;
            end if;
        end do:
        if w then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Mar 30 2017

Mathematica

Table[d = Divisors[n]; Coefficient[Series[1/Product[1 - x^d[[i]], {i, Length[d]}], {x, 0, n}], x, n], {n, 100}] (* T. D. Noe, Jul 28 2011 *)

PARI

a(n)=numbpartUsing(n, divisors(n));
numbpartUsing(n, v, mx=#v)=if(n<1, return(n==0)); sum(i=1,mx, numbpartUsing(n-v[i],v,i)) \\ inefficient; Charles R Greathouse IV, Jun 21 2017

PARI

A018818(n) = { my(p = Ser(1, 'x, 1+n)); fordiv(n, d, p /= (1 - 'x^d)); polcoef(p, n); }; \\ Antti Karttunen, Jan 23 2025, after Vladeta Jovovic

Formula

Coefficient of x^n in the expansion of 1/Product_{d|n} (1-x^d). - Vladeta Jovovic, Sep 28 2002

a(n) = 2 iff n is prime. - Juhani Heino, Aug 27 2009

a(n) = f(n,n,1), where f(n,m,k) = f(n,m,k+1) + f(n,m-k,k)*0^(n mod k) if k <= m, otherwise 0^m. - Reinhard Zumkeller, Dec 11 2009

Paul Erdős, Andrew M. Odlyzko, and the Editors of the AMM give bounds; see Bowman et al. - Charles R Greathouse IV, Dec 04 2012