×

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

References:

[1] Dress F., Experimental Math. 2 pp 93– (1993)
[2] Lagarias J., J. Algorithms 8 pp 173– (1987) · Zbl 0622.10027 · doi:10.1016/0196-6774(87)90037-X
[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 · doi:10.1515/crll.1832.9.105
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.