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

1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 1, 0, 4, 0, 3, 0, 1, 0, 5, 0, 8, 0, 2, 0, 5, 0, 10, 0, 4, 0, 13, 0, 15, 0, 3, 1, 13, 0, 19, 0, 9, 1, 24, 0, 20, 2, 13, 2, 29, 0, 34, 2, 17, 2, 34, 1, 49, 2, 21, 3, 58, 2, 63, 3, 20, 7, 72, 2, 81, 3

Offset: 31

Author

Alois P. Heinz, Dec 18 2011

Keywords

• nonn

Examples

			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) = 2: [6,10,12,15], [10,15,18].
a(53) = 4: [6,12,15,20], [15,18,20], [6,12,14,21], [14,18,21].
a(55) = 3: [10,12,15,18], [6,10,15,24], [6,21,28].
		

Links

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

Crossrefs

Cf. A200976, A018783.

Programs

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;
      if n<0 then 0
    elif n=0 then `if`(g>1, 0, 1)
    elif i<2 then 0
    else ok:= evalb(i<=n);
         for j in s while ok do ok:= igcd(i, j)>1 od;
         b(n, i-1, g, map(x->w(x, i), s)) +`if`(ok,
         b(n-i, i-1, igcd(i, g), map(x->w(x, i), {s[], 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}, Which[n<0, 0, n==0, If[g>1, 0, 1], i<2, 0, True, ok = i <= n; For[j = 1, ok && j <= Length[s], j++, ok = GCD[i, s[[j]]]>1]; b[n, i-1, g, Map[w[#, i]&, s]] + If[ok, b[n-i, i-1, GCD[i, g], Map[w[#, i]&, Union @ Append[s, i]]], 0]]]; a[n_] := b[n, n, 0, {}]; Table[a[n], {n, 31, 100}] (* Jean-François Alcover, Feb 15 2017, translated from Maple *)