A202425 Number of partitions of n into parts having pairwise common factors but no overall common factor.

1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 3, 0, 0, 1, 6, 0, 5, 0, 2, 2, 9, 0, 8, 2, 4, 3, 16, 0, 22, 5, 6, 5, 19, 2, 35, 8, 14, 6, 44, 4, 55, 13, 16, 19, 64, 6, 82, 17, 39, 31, 108, 10, 105, 40, 66, 46, 161, 14, 182, 61, 97, 72, 207, 37, 287, 85, 144, 93, 357, 59

Offset

31,7

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 31..400 (terms 31..251 from Alois P. Heinz)

Formula

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

Example

a(31) = 1: [6,10,15] = [2*3,2*5,3*5].
a(37) = 2: [6,6,10,15], [10,12,15].
a(41) = 3: [6,10,10,15], [6,15,20], [6,14,21].
a(47) = 6: [6,6,10,10,15], [10,10,12,15], [6,6,15,20], [12,15,20], [6,6,14,21], [12,14,21].
a(49) = 5: [6,6,6,6,10,15], [6,6,10,12,15], [10,12,12,15], [6,10,15,18], [10,15,24].

Maple

with(numtheory):
w:= (m, h)-> mul(`if`(j>=h, 1, j), j=factorset(m)):
b:= proc(n, i, g, s) option remember; local j, ok, si;
      if n<0 then 0
    elif 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:= igcd(i, j)>1 od;
         b(n, i-1, g, si) +`if`(ok, add(b(n-t*i, i-1, igcd(i, g),
                      si union {w(i, i)} ), t=1..iquo(n, i)), 0)
      fi
    end:
a:= n-> b(n, n, 0, {}):
seq(a(n), n=31..100);

Mathematica

w[m_, h_] := Product[If[j >= h, 1, j], {j, FactorInteger[m][[All, 1]]}]; b[n_, i_, g_, s_] := b[n, i, g, s] = Module[{j, ok, si}, Which[n<0, 0, n == 0, If[g>1, 0, 1], i<2 || MemberQ[s, 1], 0, True, ok = (i <= n); si = w[#, i]& /@ s; Do[If[ok, ok = (GCD[i, j]>1)], {j, s}]; b[n, i-1, g, si] + If[ok, Sum[b[n-t*i, i-1, GCD[i, g], si ~Union~ {w[i, i]}], {t, 1, Quotient[n, i]}], 0]]]; a[n_] := b[n, n, 0, {}]; Table[a[n], {n, 31, 100}] (* Jean-François Alcover, Feb 16 2017, translated from Maple *)
Table[Length[Select[IntegerPartitions[n], GCD@@#==1&&And@@(GCD[##]>1&)@@@Tuples[#, 2]&]], {n, 0, 40}] (* Gus Wiseman, Nov 04 2019 *)

Crossrefs

Cf. A202385, A018783.

The version with only distinct parts compared is A328672.

The Heinz numbers of these partitions are A328868.

The strict case is A202385, which is essentially the same as A318715.

The version for non-isomorphic multiset partitions is A319759.

The version for set-systems is A326364.

Intersecting partitions are A200976.

Cf. A000837, A305148, A305843, A306006, A318717, A328673, A328867.

Sequence in context: A330936 A284687 A046268 * A292374 A292376 A257685

Adjacent sequences: A202422 A202423 A202424 * A202426 A202427 A202428

Keyword

nonn

Author

Alois P. Heinz, Dec 19 2011

Status

approved