An algorithm to generate square-free numbers and to compute the Möbius function

DOI10.1016/J.JNT.2012.07.017MaRDI QIDQ1930106zbMATH OpenOpenAlexFDO

Authors F. Auil

Publication date 10 January 2013

Published in Journal of Number Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.4563, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.767.8485

zbMATH Keywords

Möbius functionRiemann hypothesissquare-free numberszeta function

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Analytic computations (11Y35) Calculation of integer sequences (11Y55)

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^6, seems to support this conjecture, and shows a total running time linear or quadratic, depending on the implementation.

Recommendations

• Fonction sommatoire de la fonction de Möbius 1. Majorations expérimentales
• Detecting squarefree numbers
• Moser-Newman phenomenon for square-free numbers
• The Möbius function and statistical mechanics
• Computing the Summation of the Möbius Function

Cites work

• A strengthening of the Nyman-Beurling criterion for the Riemann hypothesis
• scientific article; zbMATH DE number 3492781 (Why is no real title available?)
• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 3300147 (Why is no real title available?)
• scientific article; zbMATH DE number 3064333 (Why is no real title available?)
• On Beurling's real variable reformulation of the Riemann Hypothesis

Cited in

(1)

• Detecting squarefree numbers

This page was built for publication: An algorithm to generate square-free numbers and to compute the Möbius function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1930106)