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,2

Links

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

Example

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

Maple

with(numtheory):
s:= proc(m, r) option remember; mul(`if`(i<r, i, 1), i=factorset(m)) end:
g:= proc(n) option remember; `if`(n<4, n, pi(n)-nops(factorset(n))+2) end:
h:= n-> 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[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 *)

Crossrefs

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

Sequence in context: A186991 A186992 A186993 * A225232 A326824 A319210

Adjacent sequences: A186970 A186971 A186972 * A186974 A186975 A186976

Keyword

nonn

Author

Alois P. Heinz, Mar 01 2011

Status

approved