Meissel–Lehmer algorithm

Template:Short description The Meissel–Lehmer algorithm (after Ernst Meissel and Derrick Henry Lehmer) is an algorithm that computes exact values of the prime-counting function.

Description

The problem of counting the exact number of primes less than or equal to x, without actually listing them all, dates from Legendre. He observed from the Sieve of Eratosthenes that

$\pi (x)-\pi (x^{1/2})+1=\lfloor x\rfloor -\sum _i\lfloor x/p_i\rfloor +\sum _{i<j}\lfloor x/p_i{p}_j\rfloor -\dots$

where Template:Math is the floor function, which denotes the greatest integer less than or equal to Template:Mvar and the Template:Math run over all primes Template:Math.

Since the evaluation of this sum formula becomes more and more complex and confusing for large Template:Mvar, Meissel tried to simplify the counting of the numbers in the Sieve of Eratosthenes. He and Lehmer therefore introduced certain sieve functions, which are detailed below.

Key functions

Let Template:Math be the first Template:Mvar primes. For a natural number Template:Math, define

$\phi (x,a):=\left|\{n\le x:p|n⟹p>p_a\}\right|,$

which counts natural numbers no greater than Template:Mvar with all prime factors greater than Template:Math. Also define for a natural number Template:Mvar,

$P_k(x,a):=\left|\{n\le x:n=q_1{q}_2\cdots q_k,\text{with}{q}_1,\dots ,q_k>p_a\}\right|,$

which counts natural numbers no greater than Template:Mvar with exactly Template:Mvar prime factors, all greater than Template:Math. With these, we have

$\phi (x,a)=\sum _{k=0}^{\mathrm{\infty }}{P}_k(x,a),$

where the sum only has finitely many nonzero terms because Template:Math when Template:Math. Using the fact that Template:Math and Template:Math, we get

$\pi (x)=\phi (x,a)+a-1-\sum _{k=2}^{\mathrm{\infty }}{P}_k(x,a),$

which proves that one may compute Template:Math by computing Template:Math and Template:Math for Template:Math. This is what the Meissel–Lehmer algorithm does.

Formula for P_k(x, a)

For Template:Math, we get the following formula for Template:Math:

$\begin{array}{cc}{P}_2(x,a)& =\left|\{n:n\le x,n=p_b{p}_c,\text{with}a<b\le c\}\right|\\ & =\sum _{b=a+1}^{\pi (x^{1/2})}\left|\{n:n\le x,n=p_b{p}_c,\text{with}b\le c\le \pi \left(\frac{x}{p_b}\right)\}\right|\\ & =\sum _{b=a+1}^{\pi (x^{1/2})}(\pi \left(\frac{x}{p_b}\right)-(b-1))\\ & =(\genfrac{}{}{0ex}{}{a}{2})-(\genfrac{}{}{0ex}{}{\pi (x^{1/2})}{2})+\sum _{b=a+1}^{\pi (x^{1/2})}\pi \left(\frac{x}{p_b}\right).\end{array}$

For Template:Math, the identities for Template:Math can be derived similarly.

Expanding Template:Math

With the starting condition

$\phi (x,0)=\lfloor x\rfloor ,$

and the recurrence

$\phi (x,a)=\phi (x,a-1)-\phi (\frac{x}{p_a},a-1),$

each value for Template:Math can be calculated recursively.

Combining the terms

The only thing that remains to be done is evaluating Template:Math and Template:Math for Template:Math, for certain values of Template:Mvar and Template:Mvar. This can be done by direct sieving and using the above formulas.

History

Meissel already found that for Template:Math, Template:Math if Template:Math. He used the resulting equation for calculations of Template:Math for big values of Template:Mvar.

Meissel calculated Template:Math for values of Template:Mvar up to Template:Math, but he narrowly missed the correct result for the biggest value of Template:Mvar.

Using his method and an IBM 701, Lehmer was able to compute the correct value of Template:Math and missed the correct value of Template:Math by 1.

Extended algorithm

Jeffrey Lagarias, Victor Miller and Andrew Odlyzko published a realisation of the algorithm which computes Template:Math in time Template:Math and space Template:Math for any Template:Math. Upon setting Template:Math, the tree of Template:Math has Template:Math leaf nodes.

This extended Meissel-Lehmer algorithm needs less computing time than the algorithm developed by Meissel and Lehmer, especially for big values of Template:Mvar.

Further improvements of the algorithm are given by M. Deleglise and J. Rivat in 1996.