%I A109511
%S A109511 0,1,2,4,5,10,11,19,23,40,41,79,80,145,164,292,293,577,578,1096,1163,
%T A109511 2188,2189,4357,4373,8470,8726,16924,16925,33832,33833,66601,67628,
%U A109511 133165,133244,266332,266333,528478,532577,1056985,1056986,2113717
%N A109511 Number of subsets of the first n numbers having a common divisor greater 
               than 1.
%C A109511 a(n) = 2^n - A085945(n) - 1 = A000225 - A085945(n);
%C A109511 a(n) - a(n-1) = 1 iff n is prime;
%C A109511 a(p^e) = a(p^e - 1) + 2^(p^(e-1) - 1) for p prime, e>0;
%C A109511 a(p*q) = a(p*q - 1) + 2^(p-1) + 2^(q-1) - 1 for primes p<>q.
%H A109511 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               Inclusion-ExclusionPrinciple.html">Inclusion-Exclusion Principle</
               a>
%F A109511 a(n) = Sum(-mu(k) * 2^(floor(n/k)-1): 1<k<=n), mu=A008683.
%e A109511 a(6) = #{{2}, {3}, {4}, {5}, {6}, {2,4}, {2,6}, {3,6}, {4,6}, {2,4,6}} 
               = 10.
%Y A109511 Sequence in context: A167795 A138048 A057762 this_sequence A018339 A128216 
               A080735
%Y A109511 Adjacent sequences: A109508 A109509 A109510 this_sequence A109512 A109513 
               A109514
%K A109511 nonn
%O A109511 1,3
%A A109511 Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Jul 01 2005