cp's OEIS Frontend

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

%I A196719 #22 Oct 18 2020 01:49:34
%S A196719 1,2,4,7,11,16,24,31,40,52,68,79,102,115,140,175,201,218,265,284,336,
%T A196719 396,446,469,547,599,662,742,837,866,1034,1065,1153,1275,1370,1511,
%U A196719 1719,1756,1869,2030,2244,2285,2613,2656,2865,3236,3394,3441,3780,3921,4232
%N A196719 Number of subsets of {1..n} (including empty set) such that the pairwise GCDs of elements are all distinct.
%H A196719 Fausto A. C. Cariboni, <a href="/A196719/b196719.txt">Table of n, a(n) for n = 0..1500</a> (terms 1..200 from Alois P. Heinz)
%e A196719 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}.
%p A196719 b:= proc(n, s) local sn, m;
%p A196719       m:= nops(s);
%p A196719       sn:= [s[], n];
%p A196719       `if`(n<1, 1, b(n-1, s) +`if`(m*(m+1)/2 = nops(({seq(seq(
%p A196719        igcd(sn[i], sn[j]), j=i+1..m+1), i=1..m)})), b(n-1, sn), 0))
%p A196719     end:
%p A196719 a:= proc(n) option remember;
%p A196719       b(n-1, [n]) +`if`(n=0, 0, a(n-1))
%p A196719     end:
%p A196719 seq(a(n), n=0..50);
%t A196719 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]]];
%t A196719 a[n_] := a[n] = b[n-1, {n}] + If[n == 0, 0, a[n-1]];
%t A196719 Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Apr 06 2017, translated from Maple *)
%Y A196719 Cf. A143823, A196720, A196721, A196722, A196723, A196724.
%K A196719 nonn
%O A196719 0,2
%A A196719 _Alois P. Heinz_, Oct 05 2011