How to use Lehmer's formula?

219 Views Asked by At

Lehmer's formula for calculating the prime-counting function π(x) is given at http://mathworld.wolfram.com/LehmersFormula.html, but I can't figure out how to use it properly. Calculating π(3) results in a = π(1.32) = 0, b = π(1.73) = 0 and c = π(1.44) = 0. This means the result is b - a + 1 = 1, which is obviously wrong since π(3) = 2. I know there's something wrong I'm doing when interpreting the formula, and I would like to know what it is.

1

There are 1 best solutions below

2
On

The formula is spread over two lines, but is a single formula.

The first part of the formula is the Legendre formula $\phi(x,a)$, the second part is $P_2(x,a)+(a-1)$, and the last part (the double sum) is $P_3(x,a)$

Here is the general formula for which Meissel and Lehmer are only particular cases: https://mathoverflow.net/questions/297785/prime-counting-meissel-lehmer-is-there-a-general-formula (You'll also find the definitions of $P_k(x,a)$)

The second part $$P_2(x,a)=\sum\limits_{a<i\leq b}{\pi(\frac{x}{p_i})-(i-1)}$$ was split $$P_2(x,a)=\sum\limits_{a<i\leq b}{\pi(\frac{x}{p_i})} - \sum\limits_{a<i\leq b}{(i-1)}$$

and $\sum\limits_{a<i\leq b}{(i-1)}=\frac{(b-a)(b+a-1)}{2}$ was joined with the $(a-1)$ part of the general formula into $\frac{(b-a+1)(b+a-2)}{2}$