A210442 -id:A210442 - cp's OEIS frontend

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

David W. Wilson

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)

			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.

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.

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

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

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

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

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

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

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

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

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

A065205 Number of subsets of proper divisors of n that sum to n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 5, 0, 0, 0, 1, 0, 3, 0, 0, 0, 0, 0, 7, 0, 0, 0, 3, 0, 2, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 3, 0, 2, 0, 0, 0, 34, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 1, 0, 6, 0, 0, 0, 25, 0, 0, 0, 1, 0, 23, 0, 0, 0, 0, 0, 21, 0, 0, 0, 2

Offset: 1

Jonathan Ayres (jonathan.ayres(AT)btinternet.com), Oct 19 2001

nonn

Deficient and weird numbers have a(n) = 0, perfect numbers and others (see A064771) have a(n) = 1.

Number of partitions of n into distinct proper divisors of n; a(A136447(n)) = 0; a(A005835(n)) > 0; a(A064771(n)) = 1. - Reinhard Zumkeller, Jan 21 2013

			a(20) = 1 because {1, 4, 5, 10} is the only subset of proper divisors of 20 that sum to 20.
a(24) = 5 because there are five different subsets we can use to sum up to 24: {1, 2, 3, 4, 6, 8}, {1, 2, 3, 6, 12}, {1, 3, 8, 12}, {2, 4, 6, 12}, {4, 8, 12}.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)

Cf. A064771, A005835.
Cf. A065218 for records.
Cf. A027751, A210442, A211110, A033630.

a065205 n = p (a027751_row n) n where
   p _      0 = 1
   p []     _ = 0
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Jan 21 2013

a[n_] := (dd = Most[ Divisors[n] ]; cc = Array[c, Length[dd]]; Length[ {ToRules[ Reduce[ And @@ (0 <= # <= 1 &) /@ cc && dd . cc == n, cc, Integers]]}]); Table[ a[n], {n, 1, 100}] (* Jean-François Alcover, Feb 23 2012 *)

a(n,s,d)={s || (s=sigma(n)-n) || return; d||d=vecextract(divisors(n),"^-1"); while(d[#d]>n, s-=d[#d]; d=d[1..-2]); s<=n && return(s==n); if( n>d[#d], a(n-d[#d],s-d[#d],d[1..-2]), 1)+a(n,s-d[#d],d[1..-2])} \\ M. F. Hasler, May 11 2015

a(n) = A033630(n) - 1.

More terms and additional comments from Jud McCranie, Oct 21 2001

A211110 Number of partitions of n into divisors > 1 of n.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 12, 1, 3, 3, 10, 1, 15, 1, 16, 3, 3, 1, 80, 2, 3, 5, 20, 1, 94, 1, 36, 3, 3, 3, 280, 1, 3, 3, 158, 1, 154, 1, 28, 25, 3, 1, 1076, 2, 29, 3, 32, 1, 255, 3, 262, 3, 3, 1, 7026, 1, 3, 32, 202, 3, 321, 1, 40, 3, 302, 1, 12072, 1

Offset: 0

Reinhard Zumkeller, Apr 01 2012

nonn

a(A000040(n)) = 1; a(A002808(n)) > 1;
a(A001248(n)) = 2; a(A080257(n)) > 2;
a(A006881(n)) = 3; a(A033942(n)) > 3.

			a(10) = #{10, 5+5, 2+2+2+2+2} = 3;
a(11) = #{11} = 1;
a(12) = #{12, 6+6, 6+4+2, 6+3+3, 6+2+2+2, 4+4+4, 4+4+2+2, 4+3+3+2, 4+2+2+2+2, 3+3+3+3, 3+3+2+2+2, 6x2} = 12;
a(13) = #{13} = 1;
a(14) = #{14, 7+7, 2+2+2+2+2+2+2} = 3;
a(15) = #{15, 5+5+5, 3+3+3+3+3} = 3.

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

Cf. A211111, A018818, A027750.

Cf. A210442.

a211110 n = p (tail $ a027750_row n) n where
   p _      0 = 1
   p []     _ = 0
   p ks'@(k:ks) m | m < k     = 0
                  | otherwise = p ks' (m - k) + p ks m

with(numtheory):
a:= proc(n) local b, l; l:= sort([(divisors(n) minus {1})[]]):
      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

a[n_] := Module[{b, l}, l = Rest[Divisors[n]]; b[m_, i_] := b[m, i] = If[m==0, 1, If[i<1, 0, b[m, i-1] + If[l[[i]]>m, 0, b[m-l[[i]], i]]]]; b[n, Length[l]]]; a[0] = 1; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jun 30 2015, after Alois P. Heinz *)

isokp(p, n) = {for (k=1, #p, if ((p[k]==1) || (n % p[k]), return (0));); return (1);}
a(n) = {my(nb = 0); forpart(p=n, if (isokp(p,n), nb++)); nb;} \\ Michel Marcus, Jun 30 2015

A294138 Number of compositions (ordered partitions) of n into proper divisors of n.

Original entry on oeis.org

1, 0, 1, 1, 5, 1, 24, 1, 55, 19, 128, 1, 1627, 1, 741, 449, 5271, 1, 45315, 1, 83343, 3320, 29966, 1, 5105721, 571, 200389, 26425, 5469758, 1, 154004510, 1, 47350055, 226019, 9262156, 51885, 15140335649, 1, 63346597, 2044894, 14700095925, 1, 185493291000, 1, 35539518745, 478164162

Offset: 0

Ilya Gutkovskiy, Oct 23 2017

nonn

			a(4) = 5 because 4 has 3 divisors {1, 2, 4} among which 2 are proper divisors {1, 2} therefore we have [2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2] and [1, 1, 1, 1].

Amiram Eldar, Table of n, a(n) for n = 0..3359
Index entries for sequences related to compositions

Cf. A027750, A032741, A065205, A100346, A210442, A294137.

Table[d = Divisors[n]; Coefficient[Series[1/(1 - Sum[Boole[d[[k]] != n] x^d[[k]], {k, Length[d]}]), {x, 0, n}], x, n], {n, 0, 45}]

a(n) = [x^n] 1/(1 - Sum_{d|n, d < n} x^d).

a(n) = A100346(n) - 1.

A293813 Number of partitions of n into nontrivial divisors of n.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 2, 0, 3, 1, 2, 0, 11, 0, 2, 2, 9, 0, 14, 0, 15, 2, 2, 0, 79, 1, 2, 4, 19, 0, 93, 0, 35, 2, 2, 2, 279, 0, 2, 2, 157, 0, 153, 0, 27, 24, 2, 0, 1075, 1, 28, 2, 31, 0, 254, 2, 261, 2, 2, 0, 7025, 0, 2, 31, 201, 2, 320, 0, 39, 2, 301, 0, 12071, 0, 2, 35, 43, 2, 427, 0, 3073

Offset: 0

Ilya Gutkovskiy, Oct 16 2017

nonn

			a(6) = 2 because 6 has 4 divisors {1, 2, 3, 6} among which 2 are nontrivial divisors {2, 3} therefore we have [3, 3] and [2, 2, 2].

Antti Karttunen, Table of n, a(n) for n = 0..10000 (computed from the b-file of A211110 provided by Alois P. Heinz)
Index entries for sequences related to partitions

Cf. A018818, A027750, A070824, A210442, A211110, A293814.

with(numtheory):
a:= proc(n) local b, l; l:= sort([(divisors(n) minus {1, 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, Oct 16 2017

Table[d = Divisors[n]; Coefficient[Series[Product[1/(1 - Boole[d[[k]] != 1 && d[[k]] != n] x^d[[k]]), {k, Length[d]}], {x, 0, n}], x, n], {n, 0, 80}]

a(n) = [x^n] Product_{d|n, 1 < d < n} 1/(1 - x^d).

a(n) = A211110(n) - 1 for n > 1.

A327642 Number of partitions of n into divisors of n that are at most sqrt(n).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 4, 1, 5, 4, 6, 1, 19, 1, 8, 6, 25, 1, 37, 1, 36, 8, 12, 1, 169, 6, 14, 10, 64, 1, 247, 1, 81, 12, 18, 8, 1072, 1, 20, 14, 405, 1, 512, 1, 144, 82, 24, 1, 2825, 8, 146, 18, 196, 1, 1000, 12, 743, 20, 30, 1, 19858, 1, 32, 112, 969, 14, 1728, 1, 324, 24, 1105

Offset: 0

Ilya Gutkovskiy, Sep 20 2019

a(n) > n if n is in A058080 Union {0}, and, a(n) <= n if n is in A007964; indeed, a(n) = n only for n = 1. - Bernard Schott, Sep 22 2019

			The divisors of 6 are 1, 2, 3, 6 and sqrt(6) = 2.449..., so the possible partitions are 1+1+1+1+1+1 = 1+1+1+1+2 = 1+1+2+2 = 2+2+2; thus a(6) = 4. - _Bernard Schott_, Sep 22 2019

David A. Corneth, Table of n, a(n) for n = 0..9999 (first 5001 terms from Robert Israel)

Cf. A018818, A210442, A211110, A293813.

[1] cat [#RestrictedPartitions(n,{d:d in Divisors(n)| d le Sqrt(n)}):n in [1..70]]; // Marius A. Burtea, Sep 20 2019

f:= proc(n) local x, t, S;
    S:= 1;
    for t in numtheory:-divisors(n) do
      if t^2 <= n then
        S:= series(S/(1-x^t),x,n+1);
      fi
    od;
    coeff(S,x,n);
end proc:
map(f, [$0..100]); # Robert Israel, Sep 22 2019

a[n_] := SeriesCoefficient[Product[1/(1 - Boole[d <= Sqrt[n]] x^d), {d, Divisors[n]}], {x, 0, n}]; Table[a[n], {n, 0, 70}]

a(n) = [x^n] Product_{d|n, d <= sqrt(n)} 1 / (1 - x^d).
a(p) = 1, where p is prime.
a(p*q) = q+1 if p <= q are primes. - Robert Israel, Sep 22 2019

A331927 Number of compositions (ordered partitions) of n into distinct divisors of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 31, 1, 1, 1, 1, 1, 31, 1, 25, 1, 1, 1, 895, 1, 1, 1, 121, 1, 151, 1, 1, 1, 1, 1, 1135, 1, 1, 1, 865, 1, 31, 1, 1, 1, 1, 1, 11935, 1, 1, 1, 1, 1, 151, 1, 841, 1, 1, 1, 129439, 1, 1, 1, 1, 1, 127, 1, 1, 1, 1

Offset: 0

Ilya Gutkovskiy, Feb 01 2020

nonn

			a(6) = 7 because we have [6], [3, 2, 1], [3, 1, 2], [2, 3, 1], [2, 1, 3], [1, 3, 2] and [1, 2, 3].

Index entries for sequences related to compositions

Cf. A018818, A027750, A033630, A065205, A100346, A210442, A211111, A294138, A331928.

a(n)={if(n==0, 1, my(v=divisors(n)); subst(serlaplace(polcoef(prod(i=1, #v, 1 + y*x^v[i] + O(x*x^n)), n)), y, 1))} \\ Andrew Howroyd, Feb 01 2020

a(n) = A331928(n) + 1 for n > 0.

A331928 Number of compositions (ordered partitions) of n into distinct proper divisors of n.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 30, 0, 24, 0, 0, 0, 894, 0, 0, 0, 120, 0, 150, 0, 0, 0, 0, 0, 1134, 0, 0, 0, 864, 0, 30, 0, 0, 0, 0, 0, 11934, 0, 0, 0, 0, 0, 150, 0, 840, 0, 0, 0, 129438, 0, 0, 0, 0, 0, 126, 0, 0, 0, 0

Offset: 0

Ilya Gutkovskiy, Feb 01 2020

nonn

			a(6) = 6 because we have [3, 2, 1], [3, 1, 2], [2, 3, 1], [2, 1, 3], [1, 3, 2] and [1, 2, 3].

Index entries for sequences related to compositions

Cf. A018818, A027751, A033630, A065205, A100346, A210442, A211111, A294138, A331927.

a(n)={if(n==0, 1, my(v=divisors(n)); subst(serlaplace((0*y) + polcoef(prod(i=1, #v-1, 1 + y*x^v[i] + O(x*x^n)), n)), y, 1))} \\ Andrew Howroyd, Feb 01 2020

a(n) = A331927(n) - 1 for n > 0.

A357311 Number of partitions of n into divisors of n that are smaller than sqrt(n).

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 4, 1, 5, 1, 6, 1, 19, 1, 8, 6, 9, 1, 37, 1, 36, 8, 12, 1, 169, 1, 14, 10, 64, 1, 247, 1, 81, 12, 18, 8, 478, 1, 20, 14, 405, 1, 512, 1, 144, 82, 24, 1, 2825, 1, 146, 18, 196, 1, 1000, 12, 743, 20, 30, 1, 19858, 1, 32, 112, 289, 14, 1728, 1, 324, 24, 1105

Offset: 0

Ilya Gutkovskiy, Sep 23 2022

nonn

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

Cf. A018818, A210442, A293813, A327642, A357312.

a:= proc(n) option remember; uses numtheory; local b, l;
      l:= sort([select(x-> is(xm, 0, b(m-l[i], i))))
          end; forget(b):
      b(n, nops(l))
    end:
seq(a(n), n=0..70);  # Alois P. Heinz, Sep 23 2022

a[n_] := SeriesCoefficient[Product[1/(1 - Boole[d < Sqrt[n]] x^d), {d, Divisors[n]}], {x, 0, n}]; Table[a[n], {n, 0, 70}]

a(n) = [x^n] Product_{d|n, d < sqrt(n)} 1 / (1 - x^d).

cp's OEIS Frontend

A018818 Number of partitions of n into divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Formula

A065205 Number of subsets of proper divisors of n that sum to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A211110 Number of partitions of n into divisors > 1 of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

A294138 Number of compositions (ordered partitions) of n into proper divisors of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A293813 Number of partitions of n into nontrivial divisors of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A327642 Number of partitions of n into divisors of n that are at most sqrt(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A331927 Number of compositions (ordered partitions) of n into distinct divisors of n.

Views