Is it true for large N that

$$\frac{1}{log(N)} \ge \prod_{\frac{N}{2}>p>2}{\frac{p-1}{p}} + \frac{\pi{(\frac{N}{2})}}{N}$$



It is not true, let me try to explain why.

The idea is as follows:

We can count $\pi(n)$ by first counting all primes less than or equal to $n/2$ and then adding the rest. However, the other primes are exactly the ones that are relatively prime to $p_1p_2\dots p_k$ (where these are the primes smaller not exceeding $\frac{n}{2}$)

So if $\lambda$ is the fraction of numbers relatively prime to $p_1p_2\dots p_n$ in the range $\{1,2,\dots,p_k\}$ then we obtain: $\pi(n)=\pi(n/2)+n\lambda$. Basically, your bound hinges on the fact that $\lambda > \frac{\varphi(p_1p_2\dots p_k)}{p_1p_2\dots p_k}$. Which is not always the case.

Note that the same idea also works with $\sqrt{n}$.

  • $\begingroup$ Thank you very much! Then, are you saying that $\lambda > \frac{\varphi(p_1p_2\dots p_k)}{p_1p_2\dots p_k}$ is not always true? $\endgroup$ – user3141592 Dec 25 '16 at 20:10
  • $\begingroup$ yeah, although I'm trying to figure out if it holds for large values of $n$. Maybe its one of those cases where all the counterexamples are small. $\endgroup$ – Jorge Fernández Hidalgo Dec 25 '16 at 20:12
  • $\begingroup$ I really think so. The multiples of 3 would be $\frac{n}{2}\frac{1}{3} +E(n)$ where $-1/3 \le E(n) \le 1/3$. The same for number 5. $\frac{n}{2}\frac{1}{5} +E(n)$ where $-2/5 \le E(n) \le 2/5$. The we have that the number of not multiples of 3 or 5 is $\frac{n}{2} \frac{2}{3} \frac{4}{5} + E(n)$. But you have to take into account that for each prime, the maximun error term will always be lower than 0.5, and that when "sieving" the multiples of 5 you are also sieving some multiples of 3 that had already been sieved, so that this can clearly compensate E(n) for sufficiently large n. $\endgroup$ – user3141592 Dec 25 '16 at 20:18
  • $\begingroup$ you should change it to $p\leq n/2$, I haven't found a counterexample for that yet. $\endgroup$ – Jorge Fernández Hidalgo Dec 25 '16 at 20:46
  • $\begingroup$ Yes, so sorry. It's true $\endgroup$ – user3141592 Dec 25 '16 at 21:30

No, it is already false for $N=10$. We have $\pi(10)=4$, $\pi(5)=3$, so that $$ 4\ge 10\left(\frac{2}{3}\right)+3\sim 9.666 $$ is wrong.

  • $\begingroup$ And for large values of N? $\endgroup$ – user3141592 Dec 25 '16 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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