Mapes' Method

A method for computing the Prime Counting Function. Define the function

$$T_k(x,a)=(-1)^{\beta_0+\beta_1+\ldots+\beta_{a-1}}\left\lflo... ...a_0} {p_2}^{\beta_1}\cdots {p_a}^{\beta_{a-1}}}\right\rfloor ,$$ (1)

where $\left\lfloor{x}\right\rfloor$ 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}+\ldots+2^1\beta_1+2^0\beta_0.$$ (2)

The Legendre Sum 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) = \left\lfloor{x}\right\rfloor$$ (4)

$$T_1(x,3) = -\left\lfloor{x\over p_1}\right\rfloor$$ (5)

$$T_2(x,3) = -\left\lfloor{x\over p_2}\right\rfloor$$ (6)

$$T_3(x,3) = \left\lfloor{x\over p_1p_2}\right\rfloor$$ (7)

$$T_4(x,3) = -\left\lfloor{x\over p_3}\right\rfloor$$ (8)

$$T_5(x,3) = \left\lfloor{x\over p_1p_3}\right\rfloor$$ (9)

$$T_6(x,3) = \left\lfloor{x\over p_2p_3}\right\rfloor$$ (10)

$$T_7(x,3) = -\left\lfloor{x\over p_1p_2p_3}\right\rfloor .$$ (11)

Mapes' method takes time $\sim x^{0.7}$, which is slightly faster than the Lehmer-Schur Method.

See also Lehmer-Schur Method, Prime Counting Function

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.