This site is supported by donations to The OEIS Foundation.

 Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A109511 Number of subsets of the first n numbers having a common divisor greater than 1. 2

%I

%S 0,1,2,4,5,10,11,19,23,40,41,79,80,145,164,292,293,577,578,1096,1163,

%T 2188,2189,4357,4373,8470,8726,16924,16925,33832,33833,66601,67628,

%U 133165,133244,266332,266333,528478,532577,1056985,1056986,2113717

%N Number of subsets of the first n numbers having a common divisor greater than 1.

%C a(n) = 2^n - A085945(n) - 1 = A000225 - A085945(n);

%C a(n) - a(n-1) = 1 iff n is prime;

%C a(p^e) = a(p^e - 1) + 2^(p^(e-1) - 1) for p prime, e>0;

%C a(p*q) = a(p*q - 1) + 2^(p-1) + 2^(q-1) - 1 for primes p<>q.

%H Alois P. Heinz, <a href="/A109511/b109511.txt">Table of n, a(n) for n = 1..2000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html">Inclusion-Exclusion Principle</a>

%F a(n) = Sum(-mu(k) * (2^floor(n/k)-1): 1<k<=n), mu=A008683.

%e a(6) = #{{2}, {3}, {4}, {5}, {6}, {2,4}, {2,6}, {3,6}, {4,6}, {2,4,6}} = 10.

%t Table[Sum[-MoebiusMu[k] (2^Floor[n/k] - 1), {k, 2, n}], {n, 1, 41}] (* _Geoffrey Critzer_, Jan 03 2012 *)

%K nonn

%O 1,3

%A _Reinhard Zumkeller_, Jul 01 2005

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 11 22:04 EST 2018. Contains 318052 sequences. (Running on oeis4.)