×

Computing the summation of the Möbius function. (English) Zbl 1007.11083

Summary: We describe an elementary method for computing isolated values of \[ M(x)=\sum_{n\leq x}\mu(n), \] where \(\mu\) is the Möbius function. The complexity of the algorithm is \(O(x^{2/3} (\log\log x)^{1/3})\) time and \(O(x^{1/3} (\log\log x)^{2/3})\) space. Certain values of \(M(x)\) for \(x\) up to \(10^{16}\) are listed: for instance, \(M(10^{16})= -3195437\).

MSC:

11Y35 Analytic computations
11Y70 Values of arithmetic functions; tables
PDF BibTeX XML Cite
Full Text: DOI EuDML EMIS

References:

[1] Dress F., Experimental Math. 2 pp 93– (1993)
[2] Lagarias J., J. Algorithms 8 pp 173– (1987) · Zbl 0622.10027
[3] Lehman R. S., Math. Comp. 14 pp 311– (1960)
[4] Mertens F., Akad. Wiss. Wien Math.-Natur. Kl. Sitzungber. IIa 100 pp 761– (1897)
[5] Möbius A. F., J. reine angew. Math. 9 pp 105– (1832) · ERAM 009.0333cj
[6] Odlyzko A., J. reine angew. Math. 357 pp 138– (1985)
[7] Pintz J., Astérisque 147 pp 325– (1987)
[8] von Sterneck R. D., Akad. Wiss. Wien Math.-Natur. Kl. Sitzungber. IIa 121 pp 1083– (1912)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.