A072721 -id:A072721 - 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

A072720 Number of partitions of n into parts which are each powers of a single number (which may vary between partitions).

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 10, 11, 15, 17, 23, 24, 34, 35, 43, 47, 57, 58, 73, 74, 91, 96, 112, 113, 139, 141, 163, 168, 197, 198, 235, 236, 272, 279, 317, 321, 378, 379, 427, 436, 501, 502, 575, 576, 653, 666, 742, 743, 851, 853, 952, 963, 1080, 1081, 1211, 1216, 1361

Offset: 0

Henry Bottomley, Jul 05 2002

nonn

First differs from A322912 at a(12) = 34, A322912(12) = 33.

			a(6)=10 since 6 can be written as 6 (powers of 6), 5+1 (5), 4+1+1 (4 or 2), 3+3 (3), 3+1+1+1 (3), 4+2 (2), 2+2+2 (2), 2+2+1+1 (2), 2+1+1+1+1 (2) and 1+1+1+1+1+1 (powers of anything).
From _Gus Wiseman_, Jan 01 2019: (Start)
The a(1) = 1 through a(8) = 15 integer partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (22)    (41)     (33)      (61)       (44)
             (111)  (31)    (221)    (42)      (331)      (71)
                    (211)   (311)    (51)      (421)      (422)
                    (1111)  (2111)   (222)     (511)      (611)
                            (11111)  (411)     (2221)     (2222)
                                     (2211)    (4111)     (3311)
                                     (3111)    (22111)    (4211)
                                     (21111)   (31111)    (5111)
                                     (111111)  (211111)   (22211)
                                               (1111111)  (41111)
                                                          (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)
(End)

Cf. A000123, A005704, A005705, A005706, A072721.

Cf. A018819, A023893, A052410, A102430, A322900, A322901, A322902, A322903, A322912.

radbase[n_]:=n^(1/GCD@@FactorInteger[n][[All,2]]);
Table[Length[Select[IntegerPartitions[n],SameQ@@radbase/@DeleteCases[#,1]&]],{n,30}] (* Gus Wiseman, Jan 01 2019 *)

a(n) = a(n-1) + A072721(n). a(p) = a(p-1)+1 for p prime.

A322900 Number of integer partitions of n whose parts are all proper powers of the same number.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 5, 2, 5, 3, 7, 2, 11, 2, 9, 5, 11, 2, 16, 2, 18, 6, 17, 2, 27, 3, 23, 6, 30, 2, 38, 2, 37, 8, 39, 5, 58, 2, 49, 10, 66, 2, 74, 2, 78, 14, 77, 2, 109, 3, 100, 12, 118, 2, 131, 6, 146, 15, 143, 2, 190, 2, 169, 20, 203, 6, 224, 2, 242, 18, 248

Offset: 0

Gus Wiseman, Dec 30 2018

nonn

Such a partition contains either no 1's or only 1's.
A proper power of n is a number n^k for some positive integer k.
Also integer partitions whose parts all have the same radical base (A052410).

			The a(1) = 1 through a(14) = 9 integer partitions (A = 10, B = 11, C = 12, D = 13, E = 14):
  (1) (2)  (3)   (4)    (5)     (6)      (7)       (8)        (9)
      (11) (111) (22)   (11111) (33)     (1111111) (44)       (333)
                 (1111)         (42)               (422)      (111111111)
                                (222)              (2222)
                                (111111)           (11111111)
.
  (A)          (B)           (C)            (D)             (E)
  (55)         (11111111111) (66)           (1111111111111) (77)
  (82)                       (84)                           (842)
  (442)                      (93)                           (4442)
  (4222)                     (444)                          (8222)
  (22222)                    (822)                          (44222)
  (1111111111)               (3333)                         (422222)
                             (4422)                         (2222222)
                             (42222)                        (11111111111111)
                             (222222)
                             (111111111111)

a(n) = A072721(n) + 1.

Cf. A000961, A001597, A018819, A023893, A023894, A052409, A052410, A072720, A102430, A302593, A322901, A322902, A322903.

radbase[n_]:=n^(1/GCD@@FactorInteger[n][[All,2]]);
Table[Length[Select[IntegerPartitions[n],SameQ@@radbase/@#&]],{n,30}]

A322901 Numbers whose prime indices are all powers of the same number.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 34, 36, 37, 38, 40, 41, 42, 43, 44, 46, 47, 48, 49, 50, 52, 53, 54, 56, 57, 58, 59, 61, 62, 63, 64, 67, 68, 71, 72, 73, 74, 76, 79, 80, 81, 82, 83

Offset: 1

Gus Wiseman, Dec 30 2018

nonn

A prime index of n is a number m such that prime(m) divides n.

			The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k). The sequence of all integer partitions whose Heinz numbers belong to the sequence begins: (), (1), (2), (11), (3), (21), (4), (111), (22), (31), (5), (211), (6), (41), (1111), (7), (221), (8), (311), (42), (51), (9), (2111), (33), (61), (222), (411).

Cf. A001597, A018819, A052409, A052410, A056239, A072720, A072721, A302242, A302593, A322900, A322902, A322903.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
radbase[n_]:=n^(1/GCD@@FactorInteger[n][[All,2]]);
Select[Range[100],SameQ@@radbase/@DeleteCases[primeMS[#],1]&]

A322902 Numbers whose prime indices are all proper powers of the same number.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 21, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 57, 59, 61, 63, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 115, 121, 125, 127, 128, 131, 133, 137, 139, 147, 149, 151, 157, 159, 163, 167, 169

Offset: 1

Gus Wiseman, Dec 30 2018

nonn

A prime index of n is a number m such that prime(m) divides n.
A proper power of n is a number n^k for some positive integer k.
Also the union of A322903 and A000079.

			The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k). The sequence of all integer partitions whose Heinz numbers belong to the sequence begins: (), (1), (2), (11), (3), (4), (111), (22), (5), (6), (1111), (7), (8), (42), (9), (33), (222).

Cf. A001597, A018819, A023893, A023894, A052410, A056239, A072720, A072721, A302242, A302593, A322900, A322901, A322903.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
radbase[n_]:=n^(1/GCD@@FactorInteger[n][[All,2]]);
Select[Range[100],SameQ@@radbase/@primeMS[#]&]

A322903 Odd numbers whose prime indices are all proper powers of the same number.

Original entry on oeis.org

1, 3, 5, 7, 9, 11, 13, 17, 19, 21, 23, 25, 27, 29, 31, 37, 41, 43, 47, 49, 53, 57, 59, 61, 63, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 115, 121, 125, 127, 131, 133, 137, 139, 147, 149, 151, 157, 159, 163, 167, 169, 171, 173, 179, 181, 189, 191

Offset: 1

Gus Wiseman, Dec 30 2018

nonn

A prime index of n is a number m such that prime(m) divides n.

A proper power of n is a number n^k for some positive integer k.

			The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k). The sequence of all integer partitions whose Heinz numbers belong to the sequence begins: (), (2), (3), (4), (2,2), (5), (6), (7), (8), (4,2), (9), (3,3), (2,2,2), (10), (11), (12), (13), (14), (15), (4,4), (16), (8,2), (17), (18), (4,2,2), (19), (20), (21), (22), (2,2,2,2).

Cf. A001597, A018819, A023894, A052410, A056239, A072720, A072721, A302593, A322900, A322901, A322902.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
radbase[n_]:=n^(1/GCD@@FactorInteger[n][[All,2]]);
Select[Range[100],And[OddQ[#],SameQ@@radbase/@primeMS[#]]&]

A379957 Number of partitions of n where the smallest part is a divisor d > 1 of n, and the other parts are positive powers of that divisor.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 1, 4, 2, 6, 1, 9, 1, 8, 4, 9, 1, 15, 1, 15, 5, 16, 1, 23, 2, 22, 5, 25, 1, 37, 1, 31, 7, 38, 4, 49, 1, 48, 9, 55, 1, 73, 1, 66, 12, 76, 1, 93, 2, 99, 11, 101, 1, 129, 5, 124, 14, 142, 1, 167, 1, 168, 17, 174, 5, 223, 1, 211, 17, 247, 1, 269, 1, 286, 24, 293, 4, 355, 1, 347, 21, 392, 1, 432, 6, 452, 25

Offset: 1

Antti Karttunen, Jan 22 2025

nonn

			The a(2) = 1 through a(12) = 9 integer partitions (A = 10, B = 11, C = 12):
  (2)  (3)  (4)   (5)  (6)    (7)  (8)     (9)    (A)      (B)  (C)
            (22)       (33)        (44)    (333)  (55)          (66)
                       (42)        (422)          (82)          (93)
                       (222)       (2222)         (442)         (444)
                                                  (4222)        (822)
                                                  (22222)       (3333)
                                                                (4422)
                                                                (42222)
                                                                (222222)
Note how this differs from A072721 first at n=12 (that has value A072721(12)=10 instead of 9) because this doesn't count the partition (84) of 12, as although both 8 and 4 are powers of 2 (which is a divisor of 12), the 2 itself is not included in that partition as its smallest term and 8 is not a power of 4.

Antti Karttunen, Table of n, a(n) for n = 1..20000
Index entries for sequences related to partitions.

First differs from A322968 at n=16, where a(16) = 9, while A322968(16) = 10.

Cf. also A072721, A322900.

powers_of_d_reversed(n, d) = vecsort(vector(logint(n, d), i, d^i),,4);
partitions_into_parts(n, parts, from=1) = if(0==n, 1 , my(s=0); for(i=from, #parts, if(parts[i]<=n, s += partitions_into_parts(n-parts[i], parts, i))); (s));
A379957(n) = if(!n,1,sumdiv(n, d, if(1==d, 0, partitions_into_parts(n-d, powers_of_d_reversed(n, d)))));

A379957(n) = sumdiv(n, d, if(d>1, polcoef(1/prod(j=1, logint(n,d), 1 - 'x^(d^j), Ser(1, 'x, n-d+1)), n-d)));

seq(n)={Vec(sum(d=2, n, x^d/prod(j=1, logint(n,d), 1 - x^(d^j), Ser(1,x,1+n-d))), -n)} \\ Andrew Howroyd, Jan 23 2025

For all n >= 1, a(n) <= A072721(n).

G.f.: Sum_{k>=2} x^k/Product_{j>=1} (1 - x^(k^j)). - Andrew Howroyd, Jan 23 2025

A322912 Number of integer partitions of n whose parts are all powers of the same squarefree number.

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 10, 11, 15, 17, 23, 24, 33, 34, 42, 46, 56, 57, 71, 72, 88, 93, 109, 110, 134, 136, 158, 163, 191, 192, 229, 230, 266, 273, 311, 315, 370, 371, 419, 428, 491, 492, 565, 566, 642, 654, 730, 731, 836, 838, 936

Offset: 0

Gus Wiseman, Dec 30 2018

nonn

First differs from A072720 at a(12) = 33, A072720(12) = 34.

			The a(1) = 1 through a(8) = 15 integer partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (22)    (41)     (33)      (61)       (44)
             (111)  (31)    (221)    (42)      (331)      (71)
                    (211)   (311)    (51)      (421)      (422)
                    (1111)  (2111)   (222)     (511)      (611)
                            (11111)  (411)     (2221)     (2222)
                                     (2211)    (4111)     (3311)
                                     (3111)    (22111)    (4211)
                                     (21111)   (31111)    (5111)
                                     (111111)  (211111)   (22211)
                                               (1111111)  (41111)
                                                          (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)

Cf. A000961, A005117, A018819, A023893, A052410, A072720, A072721, A072774, A302593, A322847, A322900, A322901, A322911.

radbase[n_]:=n^(1/GCD@@FactorInteger[n][[All,2]]);
powsqfQ[n_]:=SameQ@@Last/@FactorInteger[n];
Table[Length[Select[IntegerPartitions[n],And[And@@powsqfQ/@#,SameQ@@radbase/@DeleteCases[#,1]]&]],{n,30}]

A322968 Number of integer partitions of n with no ones whose parts are all powers of the same squarefree number.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 4, 1, 4, 2, 6, 1, 9, 1, 8, 4, 10, 1, 14, 1, 16, 5, 16, 1, 24, 2, 22, 5, 28, 1, 37, 1, 36, 7, 38, 4, 55, 1, 48, 9, 63, 1, 73, 1, 76, 12, 76, 1, 105, 2, 98, 11, 116, 1, 128, 5, 143, 14, 142, 1, 186, 1, 168, 18, 202, 5, 223, 1, 240, 17, 247, 1, 305, 1, 286, 23

Offset: 0

Gus Wiseman, Jan 01 2019

nonn

First differs from A072721 at a(12) = 9, A072721(12) = 10.

First differs from A379957 at a(16) = 10, A379957(16) = 9.

			The a(2) = 1 through a(12) = 9 integer partitions (A = 10, B = 11):
  (2)  (3)  (4)   (5)  (6)    (7)  (8)     (9)    (A)      (B)  (66)
            (22)       (33)        (44)    (333)  (55)          (84)
                       (42)        (422)          (82)          (93)
                       (222)       (2222)         (442)         (444)
                                                  (4222)        (822)
                                                  (22222)       (3333)
                                                                (4422)
                                                                (42222)
                                                                (222222)
The a(20) = 16 integer partitions:
  (10,10), (16,4),
  (8,8,4), (16,2,2),
  (5,5,5,5), (8,4,4,4), (8,8,2,2),
  (4,4,4,4,4), (8,4,4,2,2),
  (4,4,4,4,2,2), (8,4,2,2,2,2),
  (4,4,4,2,2,2,2), (8,2,2,2,2,2,2),
  (4,4,2,2,2,2,2,2),
  (4,2,2,2,2,2,2,2,2),
  (2,2,2,2,2,2,2,2,2,2).

Andrew Howroyd, Table of n, a(n) for n = 0..10000
Index entries for sequences related to partitions.

Cf. A001597, A005117, A018819, A023893, A052410, A072720, A072721, A072774, A102430, A322900, A322903, A322911, A322912, A379957.

radbase[n_]:=n^(1/GCD@@FactorInteger[n][[All,2]]);
powsqfQ[n_]:=SameQ@@Last/@FactorInteger[n];
Table[Length[Select[IntegerPartitions[n],And[FreeQ[#,1],And@@powsqfQ/@#,SameQ@@radbase/@#]&]],{n,30}]

a(n)={if(n==0, 1, sumdiv(n, d, if(d>1&&issquarefree(d), polcoef(1/prod(j=1, logint(n, d), 1 - x^(d^j), Ser(1, x, 1+n)), n))))} \\ Andrew Howroyd, Jan 23 2025

seq(n)={Vec(1 + sum(d=2, n, if(issquarefree(d), -1 + 1/prod(j=1, logint(n, d), 1 - x^(d^j), Ser(1, x, 1+n)))))} \\ Andrew Howroyd, Jan 23 2025

From  Andrew Howroyd, Jan 23 2025: (Start)
G.f.: 1 + Sum_{k>=2} -1 + 1/Product_{j>=1} (1 - x^(A005117(k)^j)).
a(p) = 1 for prime p. (End)

a(66) onwards from Andrew Howroyd, Jan 23 2025

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

A072720 Number of partitions of n into parts which are each powers of a single number (which may vary between partitions).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A322900 Number of integer partitions of n whose parts are all proper powers of the same number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A322901 Numbers whose prime indices are all powers of the same number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A322902 Numbers whose prime indices are all proper powers of the same number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A322903 Odd numbers whose prime indices are all proper powers of the same number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A379957 Number of partitions of n where the smallest part is a divisor d > 1 of n, and the other parts are positive powers of that divisor.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

PARI

Formula

A322912 Number of integer partitions of n whose parts are all powers of the same squarefree number.

Views

Author

Keywords

Comments