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

1, 2, 4, 4, 12, 4, 28, 16, 32, 12, 116, 16, 248, 48, 72, 112, 728, 64, 1520, 192, 384, 256, 3872, 256, 3168, 736, 2752, 832, 15488, 256, 31232, 7424, 6272, 4096, 9600, 1792, 91648, 9344, 16000, 5632, 214272, 3072, 431616, 37376, 38912, 43008, 982528

Offset: 1

Author

Alois P. Heinz, Mar 01 2011

Keywords

• nonn

Examples

			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}.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..220

Crossrefs

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

Programs

Maple

with(numtheory):
s:= proc(m, r) option remember; mul(`if`(i mul(ilog[j](n), j={ithprime(i)$i=1..pi(n)} minus factorset(n)):
b:= proc(t, n, k) option remember; local c, d, h;
      if k=0 or k>n then 0
    elif k=1 then 1
    elif k=2 and t=n then `if`(n<2, 0, phi(n))
    else c:= 0;
         d:= 2-irem(t, 2);
         for h from 1 to n-1 by d do
           if igcd(t, h)=1 then c:= c +b(s(t*h, h), h, k-1) fi
         end; c
      fi
    end:
a:= n-> h(n) + add(b(s(n, n), n, k), k=1..g(n)-1):
seq(a(n), n=1..50);

Mathematica

s[m_, r_] := s[m, r] = Product[If[in, 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 *)