5
$\begingroup$

Given that $\pi(x)$ is the prime-counting function, prove that, for $n\geq 3$,

1: $\pi(2n) < \pi(n)+\frac{2n}{\log_2(n)}$

2:$ \pi(2^n) < \frac{2^{n+1}\log_2(n-1)}{n}$

For $x\geq8$ a real number, prove that

$\pi(x) < \frac{2x\log_2(\log_2(x)}{\log_2(x)}$.

I understand that I should show what I've tried, but I have no idea what to do next. The only thing I know about this function is the prime number theorem, but I don't see how that could help me here.

What's strange is that this question was part of a national olympiad exam, suggesting this can be solved using elementary mathematics.

Does anyone know if these can be solved easily, without going into too advanced mathematics? Hints would be preferred over full solutions.

Question comes from 1989 Irish Mathematical Olympiad.

$\endgroup$
4
$\begingroup$

We note that$$\binom{2n}{n} \le 4^n$$and is divisible by all primes such that $n < p < 2n$.

Prove that if $n \ge 3$ is an integer, then$$\pi(2n) < \pi(n) + {{2n}\over{\log_2(n)}}.$$

$\pi(2n) - \pi(n)$ is the number of primes such that $n < p < 2n$. If there are $k$ such primes, we have the inequality$$n^k \le 4^n \implies k < {{2n}\over{\log_2 n}} \implies \pi(2n) < \pi(n) + {{2n}\over{\log_2n}}.$$

Prove that if $n \ge 3$ is an integer, then$$\pi(2^n) < {{2^{n+1}\log_2(n-1)}\over{n}}.$$

We proceed by induction. Base case $n = 3$ is trivial to check. We have$$\pi(2^{n+1}) < \pi(2^n) + {{2^{n+1}}\over{n}} < {{2^{n+1}\log_2(n-1)}\over{n}} + {{2^{n+1}}\over{n}}.$$Let us prove$${{2^{n+1}\log_2(n-1)}\over{n}} + {{2^{n+1}}\over{n}} \le {{2^{n+2} \log_2 n}\over{n+1}}.$$Dividing $2^{n+1}$ and taking off the $\log_2$ gives$$(2n-2)^{n+1} \le n^{2n},$$which is true since$$4n \le (n+1)^2 \text{ and } n \le 2^n.$$

Deduce that, for all real numbers $x \ge 8$,$$\pi(x) < {{4x \log_2(\log_2(x))}\over{\log_2(x)}}.$$

Let$$n=\lfloor\log_2x\rfloor.$$Then$$n \le \log_2x <n+1.$$Therefore,$$\pi(x) \le \pi(2^{n+1}) \le \frac{2^{n+2}\log_2n}{n+1} \le \frac{4x \log_2(\log_2x)}{\log_2x},$$as desired.

$\endgroup$

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.