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

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

Offset

1,3

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_{k=2..n} -A008683(k) * (2^floor(n/k)-1).

a(n) = 2^n - A085945(n) - 1 = A000225(n) - 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.

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 *)

Prog

(PARI) a(n) = sum(k = 2, n, -moebius(k) * (1 << (n\k) - 1)); \\ Amiram Eldar, May 09 2025

Crossrefs

Partial sums of A178472.

Cf. A008683, A000225, A085945.

Sequence in context: A138048 A376589 A057762 * A018339 A328009 A128216

Adjacent sequences: A109508 A109509 A109510 * A109512 A109513 A109514

Keyword

nonn

Author

Reinhard Zumkeller, Jul 01 2005

Status

approved