cp's OEIS Frontend

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

%I A196720 #11 Apr 06 2017 07:51:51
%S A196720 1,2,4,8,13,25,33,61,81,116,140,256,282,530,606,692,823,1551,1653,
%T A196720 3173,3391,3805,4177,8049,8345,11524,12508,15294,16204,31692,32048,
%U A196720 63280,70834,77224,82048,91686,93597,185245,196109,212359,218223,432495,436031,867647
%N A196720 Number of subsets of {1..n} (including empty set) such that the pairwise GCDs of elements are not distinct.
%C A196720 All pairwise GCDs of each subset are equal if there are any.
%C A196720 a(n) >= A084422(n).
%H A196720 Alois P. Heinz, <a href="/A196720/b196720.txt">Table of n, a(n) for n = 0..60</a>
%e A196720 a(5) = 25: {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}, {1,2,3}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,5}, {3,4,5}, {1,2,3,5}, {1,3,4,5}.
%p A196720 b:= proc(n, s) local sn, m;
%p A196720       m:= nops(s);
%p A196720       sn:= [s[], n];
%p A196720       `if`(n<1, 1, b(n-1, s) +`if`(1 >= nops(({seq(seq(
%p A196720            igcd(sn[i], sn[j]), j=i+1..m+1), i=1..m)})), b(n-1, sn), 0))
%p A196720     end:
%p A196720 a:= proc(n) option remember;
%p A196720       b(n-1, [n]) +`if`(n=0, 0, a(n-1))
%p A196720     end:
%p A196720 seq(a(n), n=0..20);
%t A196720 b[n_, s_] := b[n, s] = With[{m = Length[s], sn = Append[s, n]}, If[n<1, 1, b[n-1, s] + If[1 >= Length[ Union @ Flatten @ Table[ Table[ GCD[ sn[[i]], sn[[j]]], {j, i+1, m+1}], {i, 1, m}]], b[n-1, sn], 0]]];
%t A196720 a[n_] := a[n] = b[n-1, {n}] + If[n == 0, 0, a[n-1]];
%t A196720 Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Apr 06 2017, translated from Maple *)
%Y A196720 Cf. A143823, A196719, A196721, A196722, A196723, A196724.
%K A196720 nonn
%O A196720 0,2
%A A196720 _Alois P. Heinz_, Oct 05 2011