An Algorithm to Generate Square-Free Numbers and to Compute the Moebius Function

2011/07/22 by Fernando Auil, Auil, Fernando
Computer Science · Mathematics · #Advanced Mathematical Identities #Analytic Number Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Mathematics and Applications #Number Theory (math.NT) #cs.DS #math.NT

paper · pdf · doi:10.48550/arxiv.1107.4563

16 pages, 4 figures

arxiv created 2011/07/22 · openalex publication_date 2011/07/22 · arxiv updated 2011/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce an algorithm that iteratively produces a sequence of natural numbers k_i and functions b_i. The number k_(i+1) arises as the first point of discontinuity of b_i above k_i. We derive a set of properties of both sequences, suggesting that (1) the algorithm produces square-free numbers k_i, (2) all the square-free numbers are generated as the output of the algorithm, and (3) the value of the Moebius function mu(k_i) can be evaluated as b_i(k_(i+1)) - b_i(k_i). The logical equivalence of these properties is rigorously proved. The question remains open if one of these properties can be derived from the definition of the algorithm. Numerical evidence, limited to 5x10⁶, seems to support this conjecture, and shows a total running time linear or quadratic, depending on the implementation.

Citations

• A strengthening of the Nyman-Beurling criterion for the Riemann hypothesis, 2

Related

• A Sequence of Beurling Functions Related to the Natural Approximation B_n Defined by an Iterative Construction Generating Square-Free Numbers k and the Value of the Mobius Function at k
• Properties of Moebius number systems
• Is it possible to compute the Moebius function without factoring?
• On (not) computing the Mobius function using bounded depth circuits
• Automated Generation of Generating Functions Related to Generalized Stern's Diatomic Arrays in the footsteps of Richard Stanley