Counting squarefree numbers in time $O(x^{2/5}(\log\log x)^{3/5})$ with a wheel reduction and an implementation up to $10^{24}$

Let Q(x) be the number of squarefree integers n <= x (A071172 for x = 10^k). We prove that Q(x) = sum_{d <= D} mu(d)*floor(x/d^2) + sum_{t <= T} (M(y_t) - M(D)) with y_t = floor(sqrt(x/t)), T = floor(x/(D+1)^2) and M the Mertens function, that the set {y_t} is closed under y -> floor(y/k) in the sense floor(y_t/k) = y_{t*k^2}, and that all M(y_t) follow from a table of M up to D by a recursion. We reduce this recursion to integers coprime to a squarefree modulus W: M(y) = sum_{e | W} mu(e)*M_W(floor(y/e)) and sum_{(k,W)=1} M_W(floor(y/k)) = 1, with the large-k part evaluated over squarefree n coprime to W through counts of coprime integers. For W = 210 the number of steps is at most (64/105)*x*D^(-3/2) instead of (8/3)*x*D^(-3/2), and the sieve visits only the 48/210 of the integers coprime to 210. The total cost is O(x^(2/5) (log log x)^(3/5)). The floating-point division of the inner loops is proved exact for numerators below 2^53. The C implementation reproduces all 22 terms of A071172 listed in the data section of the entry, computes Q(10^22) in 3.5 s, Q(10^23) in 9.4 s and Q(10^24) = 607927101854026628773299 in 27.8 s on one core, against 51.7 s for Q(10^12) by the program of the entry.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-14
DOI
https://doi.org/10.5281/zenodo.24232425
Primary Topic
Analytic Number Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Counting squarefree numbers in time $O(x^{2/5}(\log\log x)^{3/5})$ with a wheel reduction and an implementation up to $10^{24}$

Mark Kim
Zenodo (CERN European Organization for Nuclear Research)
Analytic Number Theory Research
preprint

Counting squarefree numbers in time $O(x^{2/5}(\log\log x)^{3/5})$ with a wheel reduction and an implementation up to $10^{24}$

Mark Kim
preprint en

Abstract

Let Q(x) be the number of squarefree integers n <= x (A071172 for x = 10^k). We prove that Q(x) = sum_{d <= D} mu(d)*floor(x/d^2) + sum_{t <= T} (M(y_t) - M(D)) with y_t = floor(sqrt(x/t)), T = floor(x/(D+1)^2) and M the Mertens function, that the set {y_t} is closed under y -> floor(y/k) in the sense floor(y_t/k) = y_{t*k^2}, and that all M(y_t) follow from a table of M up to D by a recursion. We reduce this recursion to integers coprime to a squarefree modulus W: M(y) = sum_{e | W} mu(e)*M_W(floor(y/e)) and sum_{(k,W)=1} M_W(floor(y/k)) = 1, with the large-k part evaluated over squarefree n coprime to W through counts of coprime integers. For W = 210 the number of steps is at most (64/105)*x*D^(-3/2) instead of (8/3)*x*D^(-3/2), and the sieve visits only the 48/210 of the integers coprime to 210. The total cost is O(x^(2/5) (log log x)^(3/5)). The floating-point division of the inner loops is proved exact for numerators below 2^53. The C implementation reproduces all 22 terms of A071172 listed in the data section of the entry, computes Q(10^22) in 3.5 s, Q(10^23) in 9.4 s and Q(10^24) = 607927101854026628773299 in 27.8 s on one core, against 51.7 s for Q(10^12) by the program of the entry.

Zenodo (CERN European Organization for Nuclear Research)
Analytic Number Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon