Deléglise, Marc; Rivat, Joël Computing the summation of the Möbius function. (English) Zbl 1007.11083 Exp. Math. 5, No. 4, 291-295 (1996). 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\). Cited in 1 ReviewCited in 7 Documents MSC: 11Y35 Analytic computations 11Y70 Values of arithmetic functions; tables Keywords:Möbius function; complexity × Cite Format Result Cite Review PDF Full Text: DOI Euclid EuDML EMIS Online Encyclopedia of Integer Sequences: Mertens’s function: Sum_{k=1..n} mu(k), where mu is the Moebius function A008683. Möbius (or Moebius) function mu(n). mu(1) = 1; mu(n) = (-1)^k if n is the product of k different primes; otherwise mu(n) = 0. a(n) is the Mertens function value at the n-th primorial number. a(n) = M(n!), the value of Mertens’s function at the n-th factorial. n such that the Moebius function take successively, from n, the values -1,0,-1,0,-1,0. Prime numbers of the form x^2+y^2 such that Mobius(x) * Mobius(y) = 1. The value of the Mertens function at n^n. 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.