Computing the summation of the Möbius function

Deléglise, Marc; Rivat, Joöl

Experiment. Math., Tome 5 (1996) no. 4, p. 291-295 / Harvested from Project Euclid

Résumé

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$.

Publié le : 1996-05-14
Classification: 11Y35

@article{1047565447,
     author = {Del\'eglise, Marc and Rivat, Jo\"ol},
     title = {Computing the summation of the M\"obius function},
     journal = {Experiment. Math.},
     volume = {5},
     number = {4},
     year = {1996},
     pages = { 291-295},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1047565447}
}

Deléglise, Marc; Rivat, Joöl. Computing the summation of the Möbius function. Experiment. Math., Tome 5 (1996) no. 4, pp.  291-295. http://gdmltest.u-ga.fr/item/1047565447/