3
$\begingroup$

I am looking for a general forumla to count prime numbers on which the Meissel and Lehmer formula are based:
$$\pi(x)=\phi(x,a)+a-1-\sum\limits_{k=2}^{\lfloor log_{p_{(a+1)}}(x) \rfloor}{P_k(x,a)}$$

Wiki - prime counting - Meissel Lehmer

More precisely, I am looking for the detailed description of the $P_k$ for $k>3$.

$P_k(x,a)$ counts the numbers$\leqslant x$ with exactly $k$ prime factors all greater than $p_a$ ($a^{th}$ prime), but in the full general formula, this last condition is not necessary.

The Meissel formula stops at $P_2$ (and still uses some $\phi$/Legendre parts)
Wolfram - Meissel

The Lehmer formula stops at $P_3$ (and still uses some $\phi$/Legendre parts)
Wolfram - Lehmer

I don't find anything about the general formula (using all the $P_k$ terms). Is there any paper on it? Why stop at $P_3$? is it a performance issue?

Lehmer vaguely talk about it in his 1959 paper
On the exact number of primes less than a given limit

Deleglise talks about performances here
Prime counting Meissel, Lehmer, ...

Thanks

Edit: by "a general formula on which the Meissel and Lehmer formula are based", I meant the one they tend to (with all $P_k$), not the one they started from (Legendre, with no $P_k$). Sorry if it was not clear.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ mathworld.wolfram.com/LegendresFormula.html ? $\endgroup$
    – Max Alekseyev
    Apr 14, 2018 at 2:52
  • $\begingroup$ Legendre (which count integers less then $x$ not divisible by the first $a$ primes) is used in the first part of the general formula: $\pi(x)=\phi(x,a)+a-1$ where $a=\pi(\sqrt[2]{x})$ if we set all $P_k=0$. Meissel go one step further by lowering $a$ and using $P_2(x,a)$ to "compensate", which is more efficient. Lehmer lowers $a$ even further. In the "full formula", Legendre part can be skipped (if we set $a=0$) and $\phi(x,a)+a-1$ become $x-1$, but this is not mandatory, we can still set $a$ to the value we want (it's a kind of cursor which "distribute the work" between $\phi$ and $P_k$). $\endgroup$
    – Collag3n
    Apr 14, 2018 at 18:13

2 Answers 2

Reset to default
6
+100
$\begingroup$

The answer to the question 'why stop at $P_3$?' is simply: because the choice $p_a^4>x$ implies $P_k=0$ for $k\geq 4$. So the papers that only include $P_2$ and $P_3$ in fact do start from the full formula with all $P_k$'s, it's just that the rest is assured to be identically zero by a judicious choice of $p_a$.

The performance gain if one takes a smaller $p_a$ so that higher $P_k$'s are nonzero is small (a factor $1/\log x$ when going from $p_a\gtrsim x^{1/3}$ to $p_a\gtrsim x^{1/4}$), at the expense of a greater complexity of the calculation. Since now polynomially faster algorithms are available (Lagarias, Miller & Odlyzko's algorithm is a factor $1/x^{1/3}$ faster than Meissel-Lehmer) there does not seem to be a motivation to speed up Meissel-Lehmer logarithmically by reducing $p_a$ below $x^{1/4}$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Yes, this is a choice. But is there any reason to make this choice? You could lower $a$ further to include $P_4$. You could do it again to include $P_5$. Why not? $\endgroup$
    – Collag3n
    Apr 15, 2018 at 20:02
  • $\begingroup$ I guess it's just that lowering $a$ adds much complexity with little gain. $\endgroup$
    – Carlo Beenakker
    Apr 16, 2018 at 6:17
  • $\begingroup$ Indeed, the sweet spot seems to be with $a=\pi(\alpha\sqrt[3]{x})$ (sweet.ua.pt/tos/bib/5.4.pdf). This is done by tweaking the algorithm, but I am still curious if there is still some gains to make by going from $P_3$ to $P_4$ and further. Outside the performance aspect, if you have any link about the $P_k$ for $k>3$, I am interested. $\endgroup$
    – Collag3n
    Apr 16, 2018 at 18:21
  • $\begingroup$ I have searched quite extensively, but all papers I found take $a$ large enough so that $P_k=0$ for $k>3$. $\endgroup$
    – Carlo Beenakker
    Apr 18, 2018 at 6:01
  • 1
    $\begingroup$ Yes, very hard to find something. I find it strange because Legendre set $a=\pi(\sqrt[2]{x})$, Meissel set $a=\pi(\sqrt[3]{x})$, and Lagarias get the best performances in between. You might think there is no point to look past Meissel, but Lehmer improve Meissel by setting $a=\pi(\sqrt[4]{x})$, so looking further might still be interesting (perhaps also with some tweaks). Anyway, thanks for the search. I think you are right, the gain is probably too small compared to the added complexity. $\endgroup$
    – Collag3n
    Apr 19, 2018 at 17:25
0
$\begingroup$

Here it is:

$$\pi(x)=\phi(x,a)+a-1-\sum\limits_{k=2}^{\lfloor log_{p_{(a+1)}}(x) \rfloor}\underbrace{{\Bigg\{ \sum\limits_{n_2=a+1}^{\pi(\sqrt[k]{x})} \sum\limits_{n_3=n_2}^{\pi\big(\sqrt[k-1]{\frac{x}{p_{n_2}}}\big)} \sum\limits_{n_4=n_3}^{\pi\Big(\sqrt[k-2]{\frac{x}{p_{n_2}\cdot p_{n_3}}}\Big)} ... \sum\limits_{n_k=n_{k-1}}^{\pi\Bigg(\sqrt[2]{\frac{x}{\prod\limits_{i=2}^{k-1}{p_{n_i}}}}\Bigg)} {\Bigg[\pi(\frac{x}{\prod\limits_{i=2}^{k}{p_{n_i}}})-\pi(p_{n_{k}})+1\Bigg]} \Bigg\}}}_{P_k(x,a)}$$

$a$ can be set to $\pi(\sqrt[{\lceil log_2(x) \rceil}]{x})=0$, so $\phi(x,a)+a-1$ become $x-1$ but as said above, $a$ can be set to any value up to $\pi(\sqrt[2]{x})$ (kindof cursor to distribute the "work" between $\phi$ and $P_k$)

(Note: $n_1=a+1$)

$\phi(x,a)+a-1$ can also be replaced by a more efficient recursive function which looks a lot like the right part (involving $\lfloor \frac{x}{\prod{p_{n_i}}} \rfloor -p_{n_k}+1$)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.