A289508 -id:A289508 - cp's OEIS frontend

A304712 Number of integer partitions of n whose parts are all equal or whose distinct parts are pairwise coprime.

1, 1, 2, 3, 5, 7, 10, 14, 19, 25, 32, 43, 54, 70, 86, 105, 130, 162, 196, 240, 286, 339, 405, 485, 573, 674, 790, 922, 1072, 1252, 1456, 1685, 1939, 2226, 2557, 2923, 3349, 3822, 4347, 4931, 5593, 6335, 7170, 8092, 9105, 10233, 11495, 12903, 14458, 16169, 18063

Offset: 0

Gus Wiseman, May 17 2018

nonn

Two parts are coprime if they have no common divisor greater than 1.

			The a(6) = 10 partitions whose parts are all equal or whose distinct parts are pairwise coprime are (6), (51), (411), (33), (321), (3111), (222), (2211), (21111), (111111).

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

Cf. A000837, A007359, A018783, A051424, A056239, A078374, A101268, A289508, A289509, A298748, A300486, A302569, A302696, A302698, A302796, A302797, A304709, A304711.

g:= proc(n, i, s) `if`(n=0, 1, `if`(i<1, 0,
      b(n, i, select(x-> x<=i, s))))
    end:
b:= proc(n, i, s) option remember; g(n, i-1, s)+(f->
     `if`(f intersect s={}, add(g(n-i*j, i-1, s union f)
        , j=1..n/i), 0))(numtheory[factorset](i))
    end:
a:= n-> g(n$2, {}):
seq(a(n), n=0..60);  # Alois P. Heinz, May 17 2018

Table[Select[IntegerPartitions[n],Or[SameQ@@#,CoprimeQ@@Union[#]]&]//Length,{n,20}]
(* Second program: *)
g[n_, i_, s_] := If[n == 0, 1, If[i < 1, 0, b[n, i, Select[s, # <= i &]]]];
b[n_, i_, s_] := b[n, i, s] = g[n, i - 1, s] + Function[f,
     If[f ~Intersection~ s == {}, Sum[g[n - i*j, i - 1, s ~Union~ f],
     {j, 1, n/i}], 0]][FactorInteger[i][[All, 1]]];
a[n_] := g[n, n, {}];
a /@ Range[0, 60] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

A305732 Heinz numbers of reducible integer partitions. Numbers n > 1 that are prime or whose prime indices are relatively prime and such that A181819(n) is already in the sequence.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 26, 28, 29, 30, 31, 32, 33, 34, 35, 37, 38, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50, 51, 52, 53, 54, 55, 56, 58, 59, 60, 61, 62, 64, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78

Offset: 1

Gus Wiseman, Jun 22 2018

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). A prime index of n is a number m such that prime(m) divides n. A multiset m whose distinct elements are m_1, m_2, ..., m_k with multiplicities y_1, y_2, ..., y_k is reducible if either m is of size 1 or gcd(m_1,...,m_k) = 1 and the multiset {y_1,...,y_k} is also reducible.

			60 has relatively prime prime indices {1,1,2,3} with multiplicities {1,1,2} corresponding to A181819(90) = 12. 12 has relatively prime prime indices {1,1,2} with multiplicities {1,2} corresponding to A181819(12) = 6. 6 has relatively prime prime indices {1,2} with multiplicities {1,1} corresponding to A181819(6) = 4. 4 has relatively prime prime indices {1,1} with multiplicities {2} corresponding to A181819(4) = 3. 3 is prime, so we conclude that 60 belongs to the sequence.

Cf. A000837, A007916, A056239, A181819, A182850, A289508, A289509, A298748, A304465, A304687, A304818, A305563, A305731, A305733.

rdzQ[n_]:=And[n>1,Or[PrimeQ[n],And[rdzQ[Times@@Prime/@FactorInteger[n][[All,2]]],GCD@@PrimePi/@FactorInteger[n][[All,1]]==1]]];
Select[Range[50],rdzQ]

A319055 Maximum product of an integer partition of n with relatively prime parts.

Original entry on oeis.org

1, 1, 2, 3, 6, 6, 12, 18, 24, 36, 54, 72, 108, 162, 216, 324, 486, 648, 972, 1458, 1944, 2916, 4374, 5832, 8748, 13122, 17496, 26244, 39366, 52488, 78732, 118098, 157464, 236196, 354294, 472392, 708588, 1062882, 1417176, 2125764, 3188646, 4251528, 6377292

Offset: 1

Gus Wiseman, Sep 09 2018

nonn

After a(7), this appears to be the same as A319054.

Cf. A000740, A000792, A000793, A000837, A001414, A007916, A100953, A281116, A289508, A289509, A296302, A319054, A319057.

Table[Max[Times@@@Select[IntegerPartitions[n],GCD@@#==1&]],{n,20}]

A366842 Number of integer partitions of n whose odd parts have a common divisor > 1.

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 1, 4, 1, 8, 3, 13, 6, 21, 10, 36, 15, 53, 28, 80, 41, 122, 63, 174, 97, 250, 140, 359, 201, 496, 299, 685, 410, 949, 575, 1284, 804, 1726, 1093, 2327, 1482, 3076, 2023, 4060, 2684, 5358, 3572, 6970, 4745, 9050, 6221, 11734, 8115, 15060, 10609

Offset: 0

Gus Wiseman, Oct 28 2023

nonn

			The a(3) = 1 through a(11) = 13 partitions:
  (3)  .  (5)    (3,3)  (7)      (3,3,2)  (9)        (5,5)      (11)
          (3,2)         (4,3)             (5,4)      (4,3,3)    (6,5)
                        (5,2)             (6,3)      (3,3,2,2)  (7,4)
                        (3,2,2)           (7,2)                 (8,3)
                                          (3,3,3)               (9,2)
                                          (4,3,2)               (4,4,3)
                                          (5,2,2)               (5,4,2)
                                          (3,2,2,2)             (6,3,2)
                                                                (7,2,2)
                                                                (3,3,3,2)
                                                                (4,3,2,2)
                                                                (5,2,2,2)
                                                                (3,2,2,2,2)

This is the odd case of A018783, complement A000837.
The even version is A047967.
The complement is counted by A366850, ranks A366846.
A000041 counts integer partitions, strict A000009.
A000740 counts relatively prime compositions.
A113685 counts partitions by sum of odds, stat A366528, w/o zeros A365067.
A168532 counts partitions by gcd.
A239261 counts partitions with (sum of odd parts) = (sum of even parts).
A289508 gives gcd of prime indices, positions of ones A289509.
Cf. A007359, A051424, A055922, A066208, A078374, A087436, A116598, A337485, A366843, A366844, A366845.

Table[Length[Select[IntegerPartitions[n], GCD@@Select[#,OddQ]>1&]], {n,0,30}]

from math import gcd
from sympy.utilities.iterables import partitions
def A366842(n): return sum(1 for p in partitions(n) if gcd(*(q for q in p if q&1))>1) # Chai Wah Wu, Oct 28 2023

A366843 Number of integer partitions of n into odd, relatively prime parts.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 3, 4, 6, 6, 9, 11, 13, 17, 21, 23, 32, 37, 42, 53, 62, 70, 88, 103, 116, 139, 164, 184, 220, 255, 283, 339, 390, 435, 511, 578, 653, 759, 863, 963, 1107, 1259, 1401, 1609, 1814, 2015, 2303, 2589, 2878, 3259, 3648, 4058, 4580, 5119, 5672, 6364

Offset: 0

Gus Wiseman, Oct 28 2023

nonn

			The a(1) = 1 through a(8) = 6 partitions:
  (1)  (11)  (111)  (31)    (311)    (51)      (331)      (53)
                    (1111)  (11111)  (3111)    (511)      (71)
                                     (111111)  (31111)    (3311)
                                               (1111111)  (5111)
                                                          (311111)
                                                          (11111111)

Allowing even parts gives A000837.
The strict case is A366844, with evens A078374.
The complement is counted by A366852, with evens A018783.
The pairwise coprime version is A366853, with evens A051424.
A000041 counts integer partitions, strict A000009 (also into odds).
A000740 counts relatively prime compositions.
A168532 counts partitions by gcd.
A366842 counts partitions whose odd parts have a common divisor > 1.
Cf. A007359, A047967, A055922, A066208, A113685, A116598, A289509, A289508, A302697, A337485, A366845, A366848, A366849.

Table[Length[Select[IntegerPartitions[n],#=={}||And@@OddQ/@#&&GCD@@#==1&]],{n,0,30}]

from math import gcd
from sympy.utilities.iterables import partitions
def A366843(n): return sum(1 for p in partitions(n) if all(d&1 for d in p) and gcd(*p)==1) # Chai Wah Wu, Oct 30 2023

A316429 Heinz numbers of integer partitions whose length is equal to their LCM.

Original entry on oeis.org

2, 6, 9, 20, 50, 56, 84, 125, 126, 176, 189, 196, 240, 294, 360, 416, 441, 540, 600, 624, 686, 810, 900, 936, 968, 1029, 1040, 1088, 1215, 1350, 1404, 1500, 1560, 2025, 2106, 2250, 2340, 2401, 2432, 2600, 2704, 3159, 3375, 3510, 3648, 3750, 3900, 4056, 5265

Offset: 1

Gus Wiseman, Jul 02 2018

A110295 is a subsequence.

			3750 is the Heinz number of (3,3,3,3,2,1), whose length and lcm are both 6.

David A. Corneth, Table of n, a(n) for n = 1..10822 (Terms <= 5 * 10^11)

Cf. A056239, A074761, A110295, A143773, A237984, A289508, A289509, A290103, A296150, A316413, A316428, A316430, A316431.

Select[Range[2,200],PrimeOmega[#]==LCM@@Cases[FactorInteger[#],{p_,k_}:>PrimePi[p]]&]

heinz(n) = my(f=factor(n), pr=f[,1]~,exps=f[,2], res=vector(vecsum(exps)), t=0); for(i = 1, #pr, pr[i] = primepi(pr[i]); for(j=1, exps[i],t++; res[t] = pr[i])); res
is(n) = my(h = heinz(n)); lcm(h)==#h \\ David A. Corneth, Jul 05 2018

A319318 Number of integer partitions of n such that every distinct submultiset has a different GCD.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 3, 3, 5, 2, 6, 5, 5, 5, 8, 5, 9, 6, 8, 9, 11, 6, 11, 11, 11, 10, 14, 9, 16, 12, 14, 15, 15, 11, 19, 17, 17, 14, 22, 15, 22, 18, 18, 21, 25, 16, 24, 21, 23, 22, 28, 21, 26, 22, 26, 27, 32, 20, 35, 30, 27, 27, 31, 27, 38, 30, 33, 29

Offset: 1

Gus Wiseman, Sep 17 2018

nonn

Note that such partitions are necessarily strict.

			The a(31) = 16 partitions are (31), (16,15), (17,14), (18,13), (19,12), (20,11), (21,10), (22,9), (23,8), (24,7), (25,6), (26,5), (27,4), (28,3), (29,2), (15,10,6).

Cf. A108917, A275972, A289508, A289509, A316313, A319315, A319319, A319320.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&UnsameQ@@GCD@@@Union[Rest[Subsets[#]]]&]],{n,30}]

A328336 Numbers with no consecutive prime indices relatively prime.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 11, 13, 17, 19, 21, 23, 25, 27, 29, 31, 37, 39, 41, 43, 47, 49, 53, 57, 59, 61, 63, 65, 67, 71, 73, 79, 81, 83, 87, 89, 91, 97, 101, 103, 107, 109, 111, 113, 115, 117, 121, 125, 127, 129, 131, 133, 137, 139, 147, 149, 151, 157, 159, 163, 167

Offset: 1

Gus Wiseman, Oct 14 2019

nonn

First differs from A318978 in having 897, with prime indices {2, 6, 9}.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), so these are Heinz numbers of partitions no consecutive parts relatively prime (A328187).
Besides the initial 1 this differs from A305078: 47541=897*prime(16) is in A305078 but not in this set. - Andrey Zabolotskiy, Nov 13 2019

			The sequence of terms together with their prime indices begins:
   1: {}
   2: {1}
   3: {2}
   5: {3}
   7: {4}
   9: {2,2}
  11: {5}
  13: {6}
  17: {7}
  19: {8}
  21: {2,4}
  23: {9}
  25: {3,3}
  27: {2,2,2}
  29: {10}
  31: {11}
  37: {12}
  39: {2,6}
  41: {13}
  43: {14}

Numbers with consecutive prime indices relatively prime are A328335.
Strict partitions with no consecutive parts relatively prime are A328220.
Numbers with relatively prime prime indices are A289509.
Cf. A000837, A056239, A078374, A112798, A281116, A289508, A318981, A328168, A328169, A328172, A328187, A328188.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],!MatchQ[primeMS[#],{_,x_,y_,_}/;GCD[x,y]==1]&]

A101391 Triangle read by rows: T(n,k) is the number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1,x_2,...,x_k) = 1 (1<=k<=n).

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 2, 3, 1, 0, 4, 6, 4, 1, 0, 2, 9, 10, 5, 1, 0, 6, 15, 20, 15, 6, 1, 0, 4, 18, 34, 35, 21, 7, 1, 0, 6, 27, 56, 70, 56, 28, 8, 1, 0, 4, 30, 80, 125, 126, 84, 36, 9, 1, 0, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0, 4, 42, 154, 325, 461, 462, 330, 165, 55, 11, 1, 0, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1

Offset: 1

Emeric Deutsch, Jan 26 2005

If instead we require that the individual parts (x_i,x_j) be relatively prime, we get A282748. This is the question studied by Shonhiwa (2006). - N. J. A. Sloane, Mar 05 2017.

			T(6,3)=9 because we have 411,141,114 and the six permutations of 123 (222 does not qualify).
T(8,3)=18 because binomial(0,2)*mobius(8/1)+binomial(1,2)*mobius(8/2)+binomial(3,2)*mobius(8/4)+binomial(7,2)*mobius(8/8)=0+0+(-3)+21=18.
Triangle begins:
   1;
   0,  1;
   0,  2,  1;
   0,  2,  3,   1;
   0,  4,  6,   4,   1;
   0,  2,  9,  10,   5,   1;
   0,  6, 15,  20,  15,   6,   1;
   0,  4, 18,  34,  35,  21,   7,   1;
   0,  6, 27,  56,  70,  56,  28,   8,   1;
   0,  4, 30,  80, 125, 126,  84,  36,   9,   1;
   0, 10, 45, 120, 210, 252, 210, 120,  45,  10,  1;
   0,  4, 42, 154, 325, 461, 462, 330, 165,  55, 11,  1;
   0, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1;
  ...
From _Gus Wiseman_, Oct 19 2020: (Start)
Row n = 6 counts the following compositions:
  (15)  (114)  (1113)  (11112)  (111111)
  (51)  (123)  (1122)  (11121)
        (132)  (1131)  (11211)
        (141)  (1212)  (12111)
        (213)  (1221)  (21111)
        (231)  (1311)
        (312)  (2112)
        (321)  (2121)
        (411)  (2211)
               (3111)
Missing are: (42), (24), (33), (222).
(End)

Alois P. Heinz, Rows n = 1..200, flattened
H. W. Gould, Binomial coefficients, the bracket function and compositions with relatively prime summands, Fib. Quart. 2(4) (1964), 241-260.
Temba Shonhiwa, Compositions with pairwise relatively prime summands within a restricted setting, Fibonacci Quart. 44 (2006), no. 4, 316-323.

Mirror image of A039911.
Row sums are A000740.
Columns 2-9 are: A000010, A000741, A000742, A000743, A023031, A023032, A023033, A023034.
A000837 counts relatively prime partitions.
A135278 counts compositions by length.
A282748 is the pairwise coprime instead of relatively prime version.
A282750 is the unordered version.
A291166 ranks these compositions (evidently).
T(2n+1,n+1) gives A000984.
Cf. A007359, A008683, A085411, A101268, A289508, A289509, A302697, A332004, A337485, A337563.

with(numtheory): T:=proc(n,k) local d, j, b: d:=divisors(n): for j from 1 to tau(n) do b[j]:=binomial(d[j]-1,k-1)*mobius(n/d[j]) od: sum(b[i],i=1..tau(n)) end: for n from 1 to 14 do seq(T(n,k),k=1..n) od; # yields the sequence in triangular form
# second Maple program:
b:= proc(n, g) option remember; `if`(n=0, `if`(g=1, 1, 0),
      expand(add(b(n-j, igcd(g, j))*x, j=1..n)))
    end:
T:= (n, k)-> coeff(b(n,0),x,k):
seq(seq(T(n,k), k=1..n), n=1..14);  # Alois P. Heinz, May 05 2025

t[n_, k_] := Sum[Binomial[d-1, k-1]*MoebiusMu[n/d], {d, Divisors[n]}]; Table[t[n, k], {n, 2, 14}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jan 20 2014 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{k}],GCD@@#==1&]],{n,10},{k,2,n}] (* change {k,2,n} to {k,1,n} for the version with zeros. - Gus Wiseman, Oct 19 2020 *)

T(n, k) = sumdiv(n, d, binomial(d-1, k-1)*moebius(n/d)); \\ Michel Marcus, Mar 09 2016

T(n,k) = Sum_{d|n} binomial(d-1,k-1)*mobius(n/d).

Sum_{k=1..n} k * T(n,k) = A085411(n). - Alois P. Heinz, May 05 2025

Definition clarified by N. J. A. Sloane, Mar 05 2017

Edited by Alois P. Heinz, May 05 2025

A303139 Number of integer partitions of n with at least two but not all parts having a common divisor greater than 1.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 5, 6, 13, 17, 33, 37, 68, 82, 125, 159, 237, 278, 409, 491, 674, 830, 1121, 1329, 1781, 2144, 2770, 3345, 4299, 5086, 6507, 7752, 9687, 11571, 14378, 16985, 21039, 24876, 30379, 35924, 43734, 51320, 62238, 73068, 87747, 103021, 123347, 143955

Offset: 1

Gus Wiseman, Apr 19 2018

nonn

			The a(7) = 5 partitions are (421), (331), (322), (2221), (22111).

Cf. A000837, A018783, A051424, A078374, A168532, A289508, A289509, A298748, A300486, A302569, A302696, A302796, A303138, A303140.

Table[Select[IntegerPartitions[n],!CoprimeQ@@#&&GCD@@#===1&]//Length,{n,30}]

cp's OEIS Frontend

A304712 Number of integer partitions of n whose parts are all equal or whose distinct parts are pairwise coprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A305732 Heinz numbers of reducible integer partitions. Numbers n > 1 that are prime or whose prime indices are relatively prime and such that A181819(n) is already in the sequence.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A319055 Maximum product of an integer partition of n with relatively prime parts.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A366842 Number of integer partitions of n whose odd parts have a common divisor > 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

A366843 Number of integer partitions of n into odd, relatively prime parts.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

A316429 Heinz numbers of integer partitions whose length is equal to their LCM.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A319318 Number of integer partitions of n such that every distinct submultiset has a different GCD.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A328336 Numbers with no consecutive prime indices relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A101391 Triangle read by rows: T(n,k) is the number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1,x_2,...,x_k) = 1 (1<=k<=n).

Views

Author

Keywords