|
Search: id:A109511
|
|
|
| A109511 |
|
Number of subsets of the first n numbers having a common divisor greater than 1. |
|
+0
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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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
|
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.
|
|
CROSSREFS
|
Sequence in context: A167795 A138048 A057762 this_sequence A018339 A128216 A080735
Adjacent sequences: A109508 A109509 A109510 this_sequence A109512 A109513 A109514
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Jul 01 2005
|
|
|
Search completed in 0.005 seconds
|
