A187106 Number of nonempty subsets of {1, 2, ..., n} having pairwise coprime elements.

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

Author

Alois P. Heinz, Mar 06 2011

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Cf. A036234. Row sums of triangle A186974. Partial sums of A186973. Rightmost elements in rows of triangle A187262.

Cf. A084422.

Programs

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

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.