login
A187106
Number of nonempty subsets of {1, 2, ..., n} having pairwise coprime elements.
15
1, 3, 7, 11, 23, 27, 55, 71, 103, 115, 231, 247, 495, 543, 615, 727, 1455, 1519, 3039, 3231, 3615, 3871, 7743, 7999, 11167, 11903, 14655, 15487, 30975, 31231, 62463, 69887, 76159, 80255, 89855, 91647, 183295, 192639, 208639, 214271, 428543
OFFSET
1,2
LINKS
FORMULA
a(n) = Sum_{k=1..A036234(n)} A186974(n,k).
a(n) = Sum_{i=1..n} A186973(i).
a(n) = A187262(n,A036234(n)).
a(n) = A084422(n) - 1.
EXAMPLE
a(4) = 11 because there are 11 nonempty subsets of {1,2,3,4} having pairwise coprime elements: {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,3,4}.
PROG
(PARI) f(n, k=1)=if(n==1, return(2)); if(gcd(k, n)==1, f(n-1, n*k)) + f(n-1, k)
a(n)=f(n)-1 \\ Charles R Greathouse IV, Aug 24 2016
CROSSREFS
Cf. A036234. Row sums of triangle A186974. Partial sums of A186973. Rightmost elements in rows of triangle A187262.
Cf. A084422.
Sequence in context: A187269 A187270 A187271 * A111668 A112038 A097452
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Mar 06 2011
STATUS
approved