info prev up next book cdrom email home

Mapes' Method

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

\begin{displaymath}
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 ,
\end{displaymath} (1)

where $\left\lfloor{x}\right\rfloor $ is the Floor Function and the $\beta_i$ are the binary digits (0 or 1) in
\begin{displaymath}
k=2^{a-1}\beta_{a-1}+2^{a-2}\beta_{a-2}+\ldots+2^1\beta_1+2^0\beta_0.
\end{displaymath} (2)

The Legendre Sum can then be written
\begin{displaymath}
\phi(x,a)=\sum_{k=0}^{2^a-1} T_k(x,a).
\end{displaymath} (3)

The first few values of $T_k(x,3)$ are
$\displaystyle T_0(x,3)$ $\textstyle =$ $\displaystyle \left\lfloor{x}\right\rfloor$ (4)
$\displaystyle T_1(x,3)$ $\textstyle =$ $\displaystyle -\left\lfloor{x\over p_1}\right\rfloor$ (5)
$\displaystyle T_2(x,3)$ $\textstyle =$ $\displaystyle -\left\lfloor{x\over p_2}\right\rfloor$ (6)
$\displaystyle T_3(x,3)$ $\textstyle =$ $\displaystyle \left\lfloor{x\over p_1p_2}\right\rfloor$ (7)
$\displaystyle T_4(x,3)$ $\textstyle =$ $\displaystyle -\left\lfloor{x\over p_3}\right\rfloor$ (8)
$\displaystyle T_5(x,3)$ $\textstyle =$ $\displaystyle \left\lfloor{x\over p_1p_3}\right\rfloor$ (9)
$\displaystyle T_6(x,3)$ $\textstyle =$ $\displaystyle \left\lfloor{x\over p_2p_3}\right\rfloor$ (10)
$\displaystyle T_7(x,3)$ $\textstyle =$ $\displaystyle -\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.




© 1996-9 Eric W. Weisstein
1999-05-26