TOPICS
Search

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

T_0(x,3)=|_x_|
(4)
T_1(x,3)=-|_x/(p_1)_|
(5)
T_2(x,3)=-|_x/(p_2)_|
(6)
T_3(x,3)=|_x/(p_1p_2)_|
(7)
T_4(x,3)=-|_x/(p_3)_|
(8)
T_5(x,3)=|_x/(p_1p_3)_|
(9)
T_6(x,3)=|_x/(p_2p_3)_|
(10)
T_7(x,3)=-|_x/(p_1p_2p_3)_|.
(11)

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