I need to show that the number of primes up to $n$ (i.e. $\pi(n)$) is $O(n/\log n)$. In the previous exercise of this question I proved that ${\displaystyle \sum_{i=1}^{\pi(n)}\log p_{i}} \leq Cn$ for some constant $C$ (where $p_i$ is the i-th prime number) . I thought I needed to do something like $${\displaystyle \sum_{i=1}^{\pi(n)}\log p_{i}\geq\sum_{i=\lfloor\pi(n)/2\rfloor}^{\pi(n)}\log p_{i}\geq\frac{\pi(n)}{2}\cdot\log p_{\frac{\pi(n)}{2}}} ,$$ and then if I show that $\log p_{\frac{\pi(n)}{2}}=O(\log n)$ then I can prove what I need, but I didn't manage to. I am kinda out of ideas right now. Any clues people?

  • 1
    $\begingroup$ This is the Prime Number Theorem. Do you need hints or an answer? I'd say there are plenty of both online $\endgroup$ – Brent J Mar 24 '13 at 22:39
  • $\begingroup$ When I searched some through the net ive found many proofs, but none of them was elementary. The point in my question is to prove it using what I proved in the first exercise. I think it should be pretty elementary. If you have any hints on what I can do from here it will be very helpful. $\endgroup$ – John Smith Mar 24 '13 at 22:45
  • $\begingroup$ I'm not sure how the sum of logs works in to the proof. I know Erdos did an elementary proof (I think there is some controversy or something) and Atle Selberg did an elementary proof. I would suggest trying to find the latter if no one ends up answering. An elementary proof is going to be pretty involved $\endgroup$ – Brent J Mar 24 '13 at 23:36
  • 3
    $\begingroup$ @BrentJ: This is much weaker than the prime number theorem. $\endgroup$ – Aryabhata Mar 29 '13 at 2:43
  • $\begingroup$ @Aryabhata you're absolutely right. Thanks for pointing that out $\endgroup$ – Brent J Mar 29 '13 at 3:07

The function you have from the previous exercise is the Chebyshev function. Let us call it $A(x)$.

You can now use Abel's identity to prove what you are seeking.

You have already shown

$$ \sum_{1 \lt k \le x} a(k) = A(x) \le cx$$

(where $a(x) = \log x$ if $x$ is prime, and $0$ otherwise)

(look at the Abel's Identity link to understand the choice of notation)

To use Abel's theorem, we take $f(x) = \frac{1}{\log x}$

And get

$$ \pi(x) = \sum_{1 \lt k \le x} \frac{a(k)}{\log k} \le \frac{cx}{\log x} + \int_{2}^{x} \frac{c}{\log ^2 t}\text{d}t = O\left(\frac{x}{\log x}\right)$$

Note: What you are trying to prove is much weaker than the prime number theorem.


Of course partial summation is the most instructive way of doing this. However here is another answer which does not depend on anything:

Assuming that we have proved $$\sum_{p \leq x} \log p \leq C x,$$ for some positive constant $C>0$ and all $x >1,$ we have $$\Big(\pi(x)-\pi(x^{\frac{1}{2}}) \Big)\log(x^{\frac{1}{2}}) \leq \sum_{x^{\frac{1}{2}}<p\leq x} \log p \leq C x.$$ Now using the trivial bound $\pi(x^{\frac{1}{2}})\leq x^{\frac{1}{2}},$ we get that $$\pi(x)\leq 2C \frac{x}{\log x}+x^{\frac{1}{2}} =O(\frac{x}{\log x}). $$


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.