A196719 Number of subsets of {1..n} (including empty set) such that the pairwise GCDs of elements are all distinct.

1, 2, 4, 7, 11, 16, 24, 31, 40, 52, 68, 79, 102, 115, 140, 175, 201, 218, 265, 284, 336, 396, 446, 469, 547, 599, 662, 742, 837, 866, 1034, 1065, 1153, 1275, 1370, 1511, 1719, 1756, 1869, 2030, 2244, 2285, 2613, 2656, 2865, 3236, 3394, 3441, 3780, 3921, 4232

Offset

0,2

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..1500 (terms 1..200 from Alois P. Heinz)

Example

a(6) = 24: {}, {1}, {2}, {3}, {4}, {5}, {6}, {1,2}, {1,3}, {1,4}, {1,5}, {1,6}, {2,3}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6}, {4,5}, {4,6}, {5,6}, {2,3,6}, {3,4,6}.

Maple

b:= proc(n, s) local sn, m;
      m:= nops(s);
      sn:= [s[], n];
      `if`(n<1, 1, b(n-1, s) +`if`(m*(m+1)/2 = nops(({seq(seq(
       igcd(sn[i], sn[j]), j=i+1..m+1), i=1..m)})), b(n-1, sn), 0))
    end:
a:= proc(n) option remember;
      b(n-1, [n]) +`if`(n=0, 0, a(n-1))
    end:
seq(a(n), n=0..50);

Mathematica

b[n_, s_] := b[n, s] = With[{m = Length[s], sn = Append[s, n]}, If[n<1, 1, b[n-1, s] + If[m*(m+1)/2 == Length[ Union @ Flatten @ Table[ Table[ GCD[ sn[[i]], sn[[j]]], {j, i+1, m+1}], {i, 1, m}]], b[n-1, sn], 0]]];
a[n_] := a[n] = b[n-1, {n}] + If[n == 0, 0, a[n-1]];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Apr 06 2017, translated from Maple *)

Crossrefs

Cf. A143823, A196720, A196721, A196722, A196723, A196724.

Sequence in context: A212364 A320591 A129339 * A011912 A063676 A099385

Adjacent sequences: A196716 A196717 A196718 * A196720 A196721 A196722

Keyword

nonn

Author

Alois P. Heinz, Oct 05 2011

Status

approved