Home Original page

Mapes' Method

A method for computing the prime counting function. Define the function

T_k(x,a)=(-1)^(beta_0+beta_1+...+beta_(a-1))|_x/(p_1^(beta_0)p_2^(beta_1)...p_a^(beta_(a-1)))_|,

(1)

where |_x_| is the floor function and the beta_i are the binary digits (0 or 1) in

k=2^(a-1)beta_(a-1)+2^(a-2)beta_(a-2)+...+2^1beta_1+2^0beta_0.

(2)

Legendre's formula can then be written

phi(x,a)=sum_(k=0)^(2^a-1)T_k(x,a).

(3)

The first few values of T_k(x,3) are

Mapes' method takes time ∼x^(0.7), which is slightly faster than the Lehmer-Schur method.

See also

Lehmer-Schur Method, Prime Counting Function

Explore with Wolfram|Alpha

References

Mapes, D. C. "Fast Method for Computing the Number of Primes Less than a Given Limit." Math. Comput. 17, 179-185, 1963.Riesel, H. "Mapes' Method." Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, p. 23, 1994.

Referenced on Wolfram|Alpha

Mapes' Method

Cite this as:

Weisstein, Eric W. "Mapes' Method." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MapesMethod.html

Subject classifications