A186973 - OEIS

%I #25 Mar 31 2016 16:51:06

%S 1,2,4,4,12,4,28,16,32,12,116,16,248,48,72,112,728,64,1520,192,384,

%T 256,3872,256,3168,736,2752,832,15488,256,31232,7424,6272,4096,9600,

%U 1792,91648,9344,16000,5632,214272,3072,431616,37376,38912,43008,982528

%N Number of subsets of {1, 2, ..., n} containing n and having pairwise coprime elements; also row sums of A186972.

%H Alois P. Heinz, <a href="/A186973/b186973.txt">Table of n, a(n) for n = 1..220</a>

%e a(6) = 4 because there are 4 subsets of {1,2,3,4,5,6} containing 6 and having pairwise coprime elements: {6}, {1,6}, {5,6}, {1,5,6}.

%p with(numtheory):

%p s:= proc(m, r) option remember; mul(`if`(i<r, i, 1), i=factorset(m)) end:

%p g:= proc(n) option remember; `if`(n<4, n, pi(n)-nops(factorset(n))+2) end:

%p h:= n-> mul(ilog[j](n), j={ithprime(i)$i=1..pi(n)} minus factorset(n)):

%p b:= proc(t, n, k) option remember; local c, d, h;

%p       if k=0 or k>n then 0

%p     elif k=1 then 1

%p     elif k=2 and t=n then `if`(n<2, 0, phi(n))

%p     else c:= 0;

%p          d:= 2-irem(t, 2);

%p          for h from 1 to n-1 by d do

%p            if igcd(t, h)=1 then c:= c +b(s(t*h, h), h, k-1) fi

%p          end; c

%p       fi

%p     end:

%p a:= n-> h(n) + add(b(s(n, n), n, k), k=1..g(n)-1):

%p seq(a(n), n=1..50);

%t s[m_, r_] := s[m, r] = Product[If[i<r, i, 1], {i, FactorInteger[m][[All, 1]]}]; a[n_] := a[n] = If[n<4, n, PrimePi[n]-Length[FactorInteger[n]]+2]; b[t_, n_, k_] := b[t, n, k] = Module[{c, d, h}, Which[k == 0 || k>n, 0, k == 1, 1, k == 2 && t == n, If[n<2, 0, EulerPhi[n]], True, c=0; d=2-Mod[t, 2]; For[h=1, h <= n-1, h=h+d, If[GCD[t, h] == 1, c=c+b[s[t*h, h], h, k-1]]]; c]]; t[n_, k_] := t[n, k] = b[s[n, n], n, k]; Table[Sum[t[n, k], {k, 1, a[n]}], {n, 1, 50}] (* _Jean-François Alcover_, Dec 04 2014, after _Alois P. Heinz_ *)

%Y Cf. A186971, A186972, A186994. Rightmost elements in rows of triangle A186975.

%K nonn

%O 1,2

%A _Alois P. Heinz_, Mar 01 2011