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
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 FunctionExplore with Wolfram|Alpha
WolframAlpha
More things to try:
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' MethodCite this as:
Weisstein, Eric W. "Mapes' Method." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MapesMethod.html