login
This site is supported by donations to The OEIS Foundation.

 

Logo


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
0, 1, 2, 4, 5, 10, 11, 19, 23, 40, 41, 79, 80, 145, 164, 292, 293, 577, 578, 1096, 1163, 2188, 2189, 4357, 4373, 8470, 8726, 16924, 16925, 33832, 33833, 66601, 67628, 133165, 133244, 266332, 266333, 528478, 532577, 1056985, 1056986, 2113717 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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

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

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

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

LINKS

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

Eric Weisstein's World of Mathematics, Inclusion-Exclusion Principle

FORMULA

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

EXAMPLE

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

MATHEMATICA

Table[Sum[-MoebiusMu[k] (2^Floor[n/k] - 1), {k, 2, n}], {n, 1, 41}]  (* Geoffrey Critzer, Jan 03 2012 *)

CROSSREFS

Sequence in context: A167795 A138048 A057762 * A018339 A128216 A080735

Adjacent sequences:  A109508 A109509 A109510 * A109512 A109513 A109514

KEYWORD

nonn

AUTHOR

Reinhard Zumkeller, Jul 01 2005

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified August 23 13:42 EDT 2017. Contains 291004 sequences.