0

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.

Eric Wofsey
  • 330,363
Måns Nilsson
  • 19

1 Answers1

1

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}$

Collag3n
  • 2,556
  • It's too slow to calculate π(10^11) because of (10^11, 78498). Plus, I was asking about Lehmer's formula. – Måns Nilsson Oct 04 '19 at 11:43
  • The special case with 3 parts explained above is the Lehmer formula (same as the one in your link). Also $a=\pi(\sqrt[4]{x})$ in that case, how do you get $78498$ for $x=10^{11}$? There is a more efficient formula in the link if your goal is to be efficient (Lagarias with $a=\pi(\alpha\sqrt[3]{x})$) – Collag3n Oct 04 '19 at 12:02