Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0869.11068
Deleglise, M.; Rivat, J.
Computing $\pi (x)$: The Meissel, Lehmer, Lagarias, Miller, Odlyzko method. (English)
[J] Math. Comput. 65, No.213, 235-245 (1996). ISSN 0025-5718; ISSN 1088-6842/e

Let, as usual, $\pi(x)$ denote the number of primes $\le x$. In 1985, {\it J. C. Lagarias}, {\it V. S. Miller} and {\it A. M. Odlyzko} [ Math. Comput. 44, 537-560 (1985; Zbl 0564.10006)] adapted a method of Meissel and Lehmer to compute single values of the function $\pi(x)$. They showed that it is possible to compute $\pi(x)$ at the expense of $ O(x^{2/3}/\log x)$ operations and $ O(x^{1/3}\log^2x\log\log x)$ space, and they applied their algorithm to compute $\pi(x)$ for selected values of $x$ up to $4\times10^{16}$. \par The paper under review presents a modified form of the above algorithm using $ O(x^{2/3}/\log^2 x)$ time and $ O(x^{1/3}\log^3x\log\log x)$ space. \par The essence of the (time) improvement is as follows. Let $p_i$ denote the $i$-th prime and let $\phi(x,a)$ denote the function which counts the numbers $\le x$ with all prime factors $> p_a$: $$\phi(x,a)=\#\{n\le x; p|n \Rightarrow p>p_a\}.$$ The major effort in the algorithm to compute $\pi(x)$ is spent on computing $\phi(x,a)$, where $a=\pi(y)$ for some suitably chosen $y\in[x^{1/3},x^{1/2}]$. One uses the recursion $\phi(x,a)=\phi(x,a-1)-\phi(x/p_a,a-1)$ with $\phi(u,0)=\lfloor u\rfloor$. This leads to the explicit formula: $$\phi(x,a)=\sum_{ 1\le n\le x, P^+(n)\le y } \mu(n)\left\lfloor {x\over n}\right\rfloor,$$ where $\mu(n)$ is the Möbius function and $P^+(n)$ is the greatest prime factor of $n$. The authors have developed an idea of Lagarias, Miller and Odlyzko to compute many terms of the sum for $\phi(x,a)$ {\it at the same time}, thus saving a $\log x$-factor in the time complexity of the algorithm. \par The authors have implemented their algorithm in C$^{++}$ and run it on an HP 730 workstation. They confirm all the values computed by Lagarias, Miller and Odlyzko (this is the first time that authors extending previous work on computing $\pi(x)$ have {\it not} found any numerical errors in the work of their immediate predecessors). Values of $\pi(x)$, $\text{ Li}(x)-\pi(x)$ and $R(x)-\pi(x)$ are listed for $x=10^{15}(10^{15})10^{16}(10^{16})10^{17}(10^{17})10^{18}$. The time to compute $\pi(4\times10^{16})$ and $\pi(10^{18})$ on the HP 730 was 42631 resp. 314754 seconds (11.8 resp. 87.4 hours). To compare: Lagarias, Miller and Odlyzko spent about 29 hours on an IBM/370 3081 to compute $\pi(4\times10^{16})$. For the given values of $x$, the reviewer has verified that $0<\text{ Li}(x)-\pi(x)<0.035\sqrt{x}$, which, prudently stated, does not tend to contradict the Riemann hypothesis. \par [Correction: the upper bound in the integral on page 244 should be $x$, rather than $\infty$].
[H.J.J.te Riele (Amsterdam)]

MSC 2000:: *11N05 Distribution of primes
11Y70 Values of arithmetic functions

Keywords: number of primes; Meissel-Lehmer method; Lagarias-Miller-Odlyzko method; algorithm; prime counting function

Citations: Zbl 0564.10006

Cited in: Zbl 1052.11086

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]