A394766 Number of squarefree composite k <= 2^n.

0, 0, 0, 1, 4, 8, 20, 46, 102, 216, 451, 935, 1926, 3953, 8061, 16407, 33301, 67436, 136359, 275334, 555435, 1119306, 2253886, 4535486, 9121429, 18334974, 36839517, 73991072, 148558353, 298185533, 598356693, 1200416017, 2407746872, 4828438274, 9681168939, 19408009855

Offset

0,5

Links

Michael De Vlieger, Table of n, a(n) for n = 0..92

Formula

a(n) = A143658(n) - A007053(n) - 1.

a(n) = (Sum_{k=1..2^(n/2)} mu(k) * floor((2^n)/k^2)) - pi(2^n) - 1, where mu = A008683 and pi = A000720.

Example

a(0)..a(2) = 0 since 6 is the smallest number in A120944.
a(3) = 1 since only 6 is no larger than 2^3 = 8.
a(4) = 4 since a(3) = 1, and additionally, 3 more numbers in A120944 are no larger than 2^4 = 16, these are {10, 14, 15}.
a(5) = 8 since a(4) = 4, and additionally, 4 more are no larger than 2^5 = 32, i.e., {21, 22, 26, 30}, etc.

Mathematica

Table[-1 + Sum[MoebiusMu[j]*Floor[(2^n)/j^2], {j, 2^(n/2)}] - PrimePi[2^n], {n, 0, 40}]

Prog

(Python)
from math import isqrt
from sympy import mobius, primepi
def A394766(n): return (m:=1<<n)+sum(mobius(k)*(m//k**2) for k in range(2, isqrt(m)+1))-primepi(m)-1 # Chai Wah Wu, Apr 12 2026

Crossrefs

Cf. A000040, A000720, A005117, A008683, A120944, A143658.

Sequence in context: A334706 A095804 A084219 * A190589 A009916 A203167

Adjacent sequences: A394763 A394764 A394765 * A394767 A394768 A394769

Keyword

nonn

Author

Michael De Vlieger, Apr 04 2026

Status

approved