|
|
A109511
|
|
Number of subsets of the first n numbers having a common divisor greater than 1.
|
|
3
|
|
|
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
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=2..n} -A008683(k) * (2^floor(n/k)-1).
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.
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|