cp's OEIS Frontend

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

%I A109511 #27 May 09 2025 07:14:31
%S A109511 0,1,2,4,5,10,11,19,23,40,41,79,80,145,164,292,293,577,578,1096,1163,
%T A109511 2188,2189,4357,4373,8470,8726,16924,16925,33832,33833,66601,67628,
%U A109511 133165,133244,266332,266333,528478,532577,1056985,1056986,2113717
%N A109511 Number of subsets of the first n numbers having a common divisor greater than 1.
%H A109511 Alois P. Heinz, <a href="/A109511/b109511.txt">Table of n, a(n) for n = 1..2000</a>
%H A109511 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html">Inclusion-Exclusion Principle</a>.
%F A109511 a(n) = Sum_{k=2..n} -A008683(k) * (2^floor(n/k)-1).
%F A109511 a(n) = 2^n - A085945(n) - 1 = A000225(n) - A085945(n);
%F A109511 a(n) - a(n-1) = 1 iff n is prime;
%F A109511 a(p^e) = a(p^e - 1) + 2^(p^(e-1) - 1) for p prime, e > 0;
%F A109511 a(p*q) = a(p*q - 1) + 2^(p-1) + 2^(q-1) - 1 for primes p <> q.
%e A109511 a(6) = #{{2}, {3}, {4}, {5}, {6}, {2,4}, {2,6}, {3,6}, {4,6}, {2,4,6}} = 10.
%t A109511 Table[Sum[-MoebiusMu[k] (2^Floor[n/k] - 1), {k, 2, n}], {n, 1, 41}]  (* _Geoffrey Critzer_, Jan 03 2012 *)
%o A109511 (PARI) a(n) = sum(k = 2, n, -moebius(k) * (1 << (n\k) - 1)); \\ _Amiram Eldar_, May 09 2025
%Y A109511 Partial sums of A178472.
%Y A109511 Cf. A008683, A000225, A085945.
%K A109511 nonn
%O A109511 1,3
%A A109511 _Reinhard Zumkeller_, Jul 01 2005