info prev up next book cdrom email home

Meissel's Formula

A modification of Legendre's Formula for the Prime Counting Function $\pi(x)$. It starts with


$\displaystyle \left\lfloor{x}\right\rfloor$ $\textstyle =$ $\displaystyle 1+\sum_{1\leq i\leq a} \left\lfloor{x\over p_i}\right\rfloor -\su...
...\sum_{1\leq i < j < k\leq a}\left\lfloor{x\over p_ip_jp_k}\right\rfloor -\ldots$  
  $\textstyle \phantom{=}$ $\displaystyle \mathop{+}\pi(x)-a+P_2(x,a)+P_3(x,a)+\ldots,$ (1)

where $\left\lfloor{x}\right\rfloor $ is the Floor Function, $P_2(x,a)$ is the number of Integers $p_ip_j\leq x$ with $a+1\leq j\leq j$, and $P_3(x,a)$ is the number of Integers $p_ip_jp_k\leq x$ with $a+1\leq i\leq j\leq k$. Identities satisfied by the $P$s include
\begin{displaymath}
P_2(x,a) = \sum\left[{\pi\left({x\over p_i}\right)-(i-1)}\right]
\end{displaymath} (2)

for $p_a<p_i\leq \sqrt{x}$ and
$\displaystyle P_3(x,a)$ $\textstyle =$ $\displaystyle \sum_{i>a} P_2\left({{x\over p_i} , a}\right)$  
  $\textstyle =$ $\displaystyle \sum_{i=a+1}^c \sum_{j=i}^{\pi(\sqrt{x/p_i})}\left[{\pi\left({x\over p_ip_j}\right)-(j-1)}\right].$ (3)

Meissel's formula is
$\displaystyle \pi(x)$ $\textstyle =$ $\displaystyle \left\lfloor{x}\right\rfloor -\sum_{i=1}^c \left\lfloor{x\over p_...
...oor +\sum_{1\leq i\leq j\leq c}\left\lfloor{x\over p_ip_j}\right\rfloor -\ldots$  
  $\textstyle \phantom{=}$ $\displaystyle +{\textstyle{1\over 2}}(b+c-2)(b-c+1)-\sum_{c\leq i\leq b} \pi\left({x\over p_i}\right),$ (4)

where
$\displaystyle b$ $\textstyle \equiv$ $\displaystyle \pi(x^{1/2})$ (5)
$\displaystyle c$ $\textstyle \equiv$ $\displaystyle \pi(x^{1/3}).$ (6)

Taking the derivation one step further yields Lehmer's Formula.

See also Legendre's Formula, Lehmer's Formula, Prime Counting Function


References

Riesel, H. ``Meissel's Formula.'' Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, p. 12, 1994.




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