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

Links

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

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

Adjacent sequences: A187103 A187104 A187105 * A187107 A187108 A187109

Keyword

nonn

Author

Alois P. Heinz, Mar 06 2011

Status

approved