A202425 -id:A202425 - cp's OEIS frontend

A328673 Number of integer partitions of n in which no two distinct parts are relatively prime.

1, 1, 2, 2, 3, 2, 5, 2, 6, 4, 9, 2, 15, 2, 17, 10, 23, 2, 39, 2, 46, 18, 58, 2, 95, 8, 103, 31, 139, 2, 219, 3, 232, 59, 299, 22, 452, 4, 492, 104, 645, 5, 920, 5, 1006, 204, 1258, 8, 1785, 21, 1994, 302, 2442, 11, 3366, 71, 3738, 497, 4570, 18, 6253, 24, 6849

Offset: 0

Gus Wiseman, Oct 29 2019

nonn

A partition with no two distinct parts relatively prime is said to be intersecting.

			The a(1) = 1 through a(10) = 9 partitions (A = 10):
  1  2   3    4     5      6       7        8         9          A
     11  111  22    11111  33      1111111  44        63         55
              1111         42               62        333        64
                           222              422       111111111  82
                           111111           2222                 442
                                            11111111             622
                                                                 4222
                                                                 22222
                                                                 1111111111

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..350

The Heinz numbers of these partitions are A328867 (strict case is A318719).
The relatively prime case is A328672.
The strict case is A318717.
The version for non-isomorphic multiset partitions is A319752.
The version for set-systems is A305843.
The version involving all parts (not just distinct ones) is A200976.
Cf. A000837, A202425, A305148, A305854, A306006, A316476, A326910.

Table[Length[Select[IntegerPartitions[n],And@@(GCD[##]>1&)@@@Subsets[Union[#],{2}]&]],{n,0,20}]

a(n > 0) = A200976(n) + 1.

A200976 Number of partitions of n such that each pair of parts (if any) has a common factor.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 14, 1, 16, 9, 22, 1, 38, 1, 45, 17, 57, 1, 94, 7, 102, 30, 138, 1, 218, 2, 231, 58, 298, 21, 451, 3, 491, 103, 644, 4, 919, 4, 1005, 203, 1257, 7, 1784, 20, 1993, 301, 2441, 10, 3365, 70, 3737, 496, 4569, 17, 6252, 23, 6848

Offset: 0

Alois P. Heinz, Nov 29 2011

nonn

a(n) is different from A018783(n) for n = 0, 31, 37, 41, 43, 46, 47, 49, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, ... .

Every pair of (possibly equal) parts has a common factor > 1. These partitions are said to be (pairwise) intersecting. - Gus Wiseman, Nov 04 2019

			a(0) = 1: [];
a(4) = 2: [2,2], [4];
a(9) = 3: [3,3,3], [3,6], [9];
a(31) = 2: [6,10,15], [31];
a(41) = 4: [6,10,10,15], [6,15,20], [6,14,21], [41].

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..350 (terms 0..250 from Alois P. Heinz)
L. Naughton, G. Pfeiffer, Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group, J. Int. Seq. 16 (2013) #13.5.8

Cf. A018783.
The version with only distinct parts compared is A328673.
The relatively prime case is A202425.
The strict case is A318717.
The version for non-isomorphic multiset partitions is A319752.
The version for set-systems is A305843.
Cf. A000837, A305148, A305854, A306006, A316476, A328672, A328867, A328868.

b:= proc(n, j, s) local ok, i;
      if n=0 then 1
    elif j<2 then 0
    else ok:= true;
         for i in s while ok do ok:= evalb(igcd(i, j)<>1) od;
         `if`(ok, add(b(n-j*k, j-1, [s[], j]), k=1..n/j), 0) +b(n, j-1, s)
      fi
    end:
a:= n-> b(n, n, []):
seq(a(n), n=0..62);

b[n_, j_, s_] := Module[{ok, i, is}, Which[n == 0, 1, j < 2, 0, True, ok = True; For[is = 1, is <= Length[s] && ok, is++, i = s[[is]]; ok = GCD[i, j] != 1]; If[ok, Sum[b[n-j*k, j-1, Append[s, j]], {k, 1, n/j}], 0] + b[n, j-1, s]]]; a[n_] := b[n, n, {}]; Table[a[n], {n, 0, 62}] (* Jean-François Alcover, Dec 26 2013, translated from Maple *)
Table[Length[Select[IntegerPartitions[n],And[And@@(GCD[##]>1&)@@@Select[Tuples[Union[#],2],LessEqual@@#&]]&]],{n,0,20}] (* Gus Wiseman, Nov 04 2019 *)

a(n > 0) = A328673(n) - 1. - Gus Wiseman, Nov 04 2019

A284825 Number of partitions of n into 3 parts without common divisors such that every pair of them has common divisors.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 3, 0, 5, 0, 0, 0, 1, 0, 5, 0, 1, 0, 6, 0, 6, 0, 0, 0, 4, 0, 6, 0, 0, 0, 9, 0, 2, 1, 2, 0, 9, 0, 8, 1, 1, 0, 5, 0, 14, 0, 1, 0, 15, 0, 14, 0, 0, 1, 14, 0, 14, 0, 2, 0, 15, 0, 6, 1, 2, 1, 11, 0, 18, 1, 1, 0, 10, 0, 23

Offset: 31

Alois P. Heinz, Apr 03 2017

The Heinz numbers of these partitions are the intersection of A014612 (triples), A289509 (relatively prime), and A337694 (pairwise non-coprime). - Gus Wiseman, Oct 16 2020

			a(31) = 1: [6,10,15] = [2*3,2*5,3*5].
a(41) = 2: [6,14,21], [6,15,20].
From _Gus Wiseman_, Oct 14 2020: (Start)
Selected terms and the corresponding triples:
  a(31)=1: a(41)=2: a(59)=3:  a(77)=4:  a(61)=5:  a(71)=6:
-------------------------------------------------------------
  15,10,6  20,15,6  24,20,15  39,26,12  33,22,6   39,26,6
           21,14,6  24,21,14  42,20,15  40,15,6   45,20,6
                    35,14,10  45,20,12  45,10,6   50,15,6
                              50,15,12  28,21,12  35,21,15
                                        36,15,10  36,20,15
                                                  36,21,14
(End)

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

Cf. A082024, A230034, A230035.
A023023 does not require pairwise non-coprimality, with strict case A101271.
A202425 and A328672 count these partitions of any length, ranked by A328868.
A284825*6 is the ordered version.
A307719 is the pairwise coprime instead of non-coprime version.
A337599 does not require relatively primality, with strict case A337605.
A200976 and A328673 count pairwise non-coprime partitions.
A289509 gives Heinz numbers of relatively prime partitions.
A327516 counts pairwise coprime partitions, ranked by A333227.
A337694 gives Heinz numbers of pairwise non-coprime partitions.
Cf. A000217, A000741, A001399, A007304, A014612, A220377, A318716, A328679, A337604, A337666.

a:= proc(n) option remember; add(add(`if`(igcd(i, j)>1
      and igcd(i, j, n-i-j)=1 and igcd(i, n-i-j)>1 and
      igcd(j, n-i-j)>1, 1, 0), j=i..(n-i)/2), i=2..n/3)
    end:
seq(a(n), n=31..137);

a[n_] := a[n] = Sum[Sum[If[GCD[i, j] > 1 && GCD[i, j, n - i - j] == 1 && GCD[i, n - i - j] > 1 && GCD[j, n - i - j] > 1, 1, 0], {j, i, (n - i)/2} ], {i, 2, n/3}];
Table[a[n], {n, 31, 137}] (* Jean-François Alcover, Jun 13 2018, from Maple *)
stabQ[u_,Q_]:=And@@Not/@Q@@@Tuples[u,2];
Table[Length[Select[IntegerPartitions[n,{3}],GCD@@#==1&&stabQ[#,CoprimeQ]&]],{n,31,100}] (* Gus Wiseman, Oct 14 2020 *)

a(n) > 0 iff n in { A230035 }.

a(n) = 0 iff n in { A230034 }.

A328672 Number of integer partitions of n with relatively prime parts in which no two distinct parts are relatively prime.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 4, 1, 4, 1, 1, 2, 7, 1, 6, 1, 3, 3, 10, 1, 9, 3, 5, 4, 17, 1, 23, 6, 7, 6, 20, 3, 36, 9, 15, 7, 45, 5, 56, 14, 17, 20, 65, 7, 83, 18, 40

Offset: 0

Gus Wiseman, Oct 29 2019

nonn

Positions of terms greater than 1 are {31, 37, 41, 43, 46, 47, 49, ...}.

A partition with no two distinct parts relatively prime is said to be intersecting.

			Examples:
  a(31) = 2:         a(46) = 2:
    (15,10,6)          (15,15,10,6)
    (1^31)             (1^46)
  a(37) = 3:         a(47) = 7:
    (15,12,10)         (20,15,12)
    (15,10,6,6)        (21,14,12)
    (1^37)             (20,15,6,6)
  a(41) = 4:           (21,14,6,6)
    (20,15,6)          (15,12,10,10)
    (21,14,6)          (15,10,10,6,6)
    (15,10,10,6)       (1^47)
    (1^41)           a(49) = 6:
  a(43) = 4:           (24,15,10)
    (18,15,10)         (18,15,10,6)
    (15,12,10,6)       (15,12,12,10)
    (15,10,6,6,6)      (15,12,10,6,6)
    (1^43)             (15,10,6,6,6,6)
                       (1^39)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..400

The Heinz numbers of these partitions are A328679.
The strict case is A318715.
The version for non-isomorphic multiset partitions is A319759.
Relatively prime partitions are A000837.
Intersecting partitions are A328673.
Cf. A078374, A285573, A289509, A291166, A303140, A305148, A316476, A326910, A326912.

Table[Length[Select[IntegerPartitions[n],GCD@@#==1&&And[And@@(GCD[##]>1&)@@@Subsets[Union[#],{2}]]&]],{n,0,32}]

a(n > 0) = A202425(n) + 1.

A328868 Heinz numbers of integer partitions with no two (not necessarily distinct) parts relatively prime, but with no divisor in common to all of the parts.

Original entry on oeis.org

17719, 40807, 43381, 50431, 74269, 83143, 101543, 105703, 116143, 121307, 123469, 139919, 140699, 142883, 171613, 181831, 185803, 191479, 203557, 205813, 211381, 213239, 215267, 219271, 230347, 246703, 249587, 249899, 279371, 286897, 289007, 296993, 300847

Offset: 1

Gus Wiseman, Oct 30 2019

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			The sequence of terms together with their prime indices begins:
   17719: {6,10,15}
   40807: {6,14,21}
   43381: {6,15,20}
   50431: {10,12,15}
   74269: {6,10,45}
   83143: {10,15,18}
  101543: {6,21,28}
  105703: {6,15,40}
  116143: {12,14,21}
  121307: {10,15,24}
  123469: {12,15,20}
  139919: {6,15,50}
  140699: {6,22,33}
  142883: {6,10,75}
  171613: {6,14,63}
  181831: {6,20,45}
  185803: {10,14,35}
  191479: {14,18,21}
  203557: {15,18,20}
  205813: {10,15,36}
  211381: {10,12,45}
  213239: {6,15,70}
  215267: {6,10,105}
  219271: {6,26,39}
  230347: {6,6,10,15}

These are the Heinz numbers of the partitions counted by A202425.
Terms of A328679 that are not powers of 2.
The strict case is A318716 (preceded by 2).
A ranking using binary indices (instead of prime indices) is A326912.
Heinz numbers of relatively prime partitions are A289509.
Cf. A000837, A056239, A112798, A200976, A291166, A302796, A316476, A318715, A319752, A319759, A328336, A328672, A328677, A328867.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
dv=Select[Range[100000],GCD@@primeMS[#]==1&&And[And@@(GCD[##]>1&)@@@Tuples[Union[primeMS[#]],2]]&]

A328679 Heinz numbers of integer partitions with no two distinct parts relatively prime, but with no divisor in common to all of the parts.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 17719, 32768, 40807, 43381, 50431, 65536, 74269, 83143, 101543, 105703, 116143, 121307, 123469, 131072, 139919, 140699, 142883, 171613, 181831, 185803, 191479, 203557, 205813, 211381, 213239

Offset: 1

Gus Wiseman, Oct 30 2019

nonn

Equals the union A000079 and A328868.
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).
A partition with no two distinct parts relatively prime is said to be intersecting.

			The sequence of terms together with their prime indices begins:
      1: {}
      2: {1}
      4: {1,1}
      8: {1,1,1}
     16: {1,1,1,1}
     32: {1,1,1,1,1}
     64: {1,1,1,1,1,1}
    128: {1,1,1,1,1,1,1}
    256: {1,1,1,1,1,1,1,1}
    512: {1,1,1,1,1,1,1,1,1}
   1024: {1,1,1,1,1,1,1,1,1,1}
   2048: {1,1,1,1,1,1,1,1,1,1,1}
   4096: {1,1,1,1,1,1,1,1,1,1,1,1}
   8192: {1,1,1,1,1,1,1,1,1,1,1,1,1}
  16384: {1,1,1,1,1,1,1,1,1,1,1,1,1,1}
  17719: {6,10,15}
  32768: {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
  40807: {6,14,21}
  43381: {6,15,20}
  50431: {10,12,15}
  65536: {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

These are the Heinz numbers of the partitions counted by A328672.
Terms that are not powers of 2 are A328868.
The strict case is A318716.
The version without global relative primality is A328867.
A ranking using binary indices (instead of prime indices) is A326912.
The version for non-isomorphic multiset partitions is A319759.
The version for divisibility (instead of relative primality) is A328677.
Heinz numbers of relatively prime partitions are A289509.
Cf. A000837, A056239, A112798, A200976, A202425, A289509, A291166, A302796, A316476, A318715, A319752, A328336.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[10000],#==1||GCD@@primeMS[#]==1&&And[And@@(GCD[##]>1&)@@@Subsets[Union[primeMS[#]],{2}]]&]

A202523 Number of partitions of n into distinct parts having pairwise prime GCDs but no overall common factor.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 2, 0, 4, 0, 0, 0, 1, 0, 4, 0, 1, 0, 5, 0, 4, 0, 0, 0, 3, 0, 5, 0, 0, 0, 6, 0, 1, 1, 2, 0, 6, 0, 6, 1, 1, 0, 4, 0, 12, 0, 1, 1, 12, 1, 9, 0, 0, 1, 10, 0, 10, 0, 1, 2, 10, 1, 4

Offset: 31

Alois P. Heinz, Dec 20 2011

nonn

			a(31) = 1: [6,10,15] = [2*3,2*5,3*5].
a(37) = 1: [10,12,15] = [2*5,2*2*3,3*5].
a(41) = 2: [6,15,20], [6,14,21].
a(43) = 1: [10,15,18].
a(47) = 1: [12,14,21].
a(49) = 1: [10,15,24].
a(61) = 4: [6,22,33], [10,15,36], [6,15,40], [6,10,45].

Alois P. Heinz, Table of n, a(n) for n = 31..251

Cf. A202385, A202425, A200976, A018783.

w:=(m, h)-> mul(`if`(j[1]>=h, 1, j[1]^min(j[2], 2)), j=ifactors(m)[2]):
b:= proc(n, i, g, s) option remember; local j, ok, si;
      if n=0 then `if`(g>1, 0, 1)
    elif i<2 or member(1, s) then 0
    else ok:= evalb(i<=n);
         si:= map(x->w(x, i), s);
         for j in s while ok do ok:= isprime(igcd(i, j)) od;
         b(n, i-1, g, si) +`if`(ok,
         b(n-i, i-1, igcd(i, g), si union {w(i, i)} ), 0)
      fi
    end:
a:= n-> b(n, n, 0, {}):
seq(a(n), n=31..100);

w[m_, h_] := Product[If[j[[1]] >= h, 1, j[[1]]^Min[j[[2]], 2]], {j, FactorInteger[m]}];
b[n_, i_, g_, s_] := b[n, i, g, s] = Module[{j, ok, si}, Which[n == 0, If[g > 1, 0, 1], i < 2 || MemberQ[s, 1], 0, True, ok = i <= n; si = w[#, i]& /@ s; For[j = 1, j <= Length[s], j++, If[!ok, Break[]]; ok = PrimeQ[ GCD[i, s[[j]]]]]; b[n, i - 1, g, si] + If[ok, b[n - i, i - 1, GCD[i, g], si ~Union~ {w[i, i]}], 0]]];
a[n_] := b[n, n, 0, {}];
Table[a[n], {n, 31, 100}] (* Jean-François Alcover, Dec 05 2020, after Alois P. Heinz *)

cp's OEIS Frontend

A328673 Number of integer partitions of n in which no two distinct parts are relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A200976 Number of partitions of n such that each pair of parts (if any) has a common factor.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A284825 Number of partitions of n into 3 parts without common divisors such that every pair of them has common divisors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A328672 Number of integer partitions of n with relatively prime parts in which no two distinct parts are relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A328868 Heinz numbers of integer partitions with no two (not necessarily distinct) parts relatively prime, but with no divisor in common to all of the parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A328679 Heinz numbers of integer partitions with no two distinct parts relatively prime, but with no divisor in common to all of the parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A202523 Number of partitions of n into distinct parts having pairwise prime GCDs but no overall common factor.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica