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

Author

Reinhard Zumkeller, Jul 01 2005

Keywords

• nonn

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..2000
• Eric Weisstein's World of Mathematics, Inclusion-Exclusion Principle.

Crossrefs

Partial sums of A178472.

Cf. A008683, A000225, A085945.

Programs

Mathematica

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

PARI

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

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.