Show that $\pi\left(n\right)\geq\log_{2}\left(\log_{2}\left(n-1\right)\right)$

Question

I need to show that $$ \pi\left(n\right)\geq\log_{2}\left(\log_{2}\left(n-1\right)\right) $$ where $\pi\left(n\right)=\left|\left\{ p\mid p\text{ is prime and }p\leq n\right\} \right|$

Now i somehow think it is related with Fermat Numbers as we saw them in class and because it is sufficient to show that $$ F_{\pi\left(n\right)}:=2^{2^{\pi(n)}}+1\geq n $$

But i'm not sure how to do it. any help?

Thanks in advance

Answer 1

Let $p_1,p_2,p_3,\ldots$ be the increasing sequence of prime natural numbers. Without Bertrand's Postulate, you can show that $p_{n+1}\leq p_1p_2\cdots p_n+1$ for every positive integer $n$. By induction, $$p_{n} \leq 2^{2^{n-1}}$$ for every positive integer $n$ (and the equality holds iff $n=1$).

Now, for a fixed real number $x>2$, let $k:=\pi(x)$. Then, we see that $x<p_{k+1} \leq p_1p_2\cdots p_k+1$, or $$x-1<p_1p_2\cdots p_k\leq 2^{2^0}\,2^{2^1}\,\cdots \,2^{2^{k-1}}=2^{2^k-1}<2^{2^k}\,.$$ That is, $$\pi(x)=k>\log_2\big(\log_2(x-1)\big)\text{ for all }x>2\,.$$

In fact, if Bertrand's Postulate is used, then we have $p_n\leq 2^{n-1}$ for all $n\geq 4$. Thus, for any real number $x\geq 5$, we have $$x<p_{k+1}\leq 2^k\,,$$ where $k:=\pi(x)\geq 3$. That is, $$\pi(x)=k>\log_2(x)\text{ for all }x\geq 5\,.$$

Answer 2

Enumerate the primes as $p_1,p_2,\dots$. If $n=p_1p_2\cdots p_k+1$, then $n$ is not divisible by any of the primes $p_1,\dots,p_k$. But $n$ is divisible by some prime. In particular, we have $p_{k+1}\leq 1+\prod_{i=1}^k p_i$ for all $k$. Now show by induction that this means $p_n\leq 2^{2^{n-1}}$.

Answer 3

A useful estimate is $$2^{\pi(n)}≥ \sqrt n$$

Proof: every natural number less than $n$ can be written uniquely as $$m^2\prod p_i^{\epsilon_i}$$

where the product is taken over all the primes $≤n$ and $\epsilon_i\in \{0,1\}$. There are $\sqrt n$ possible choices for $m$ and at most $2^{\pi(n)}$ ways to choose the $\epsilon's$.

That inequality is stronger than what you want, at least for large $n$. Indeed. it implies at once that $$\pi(x)≥\frac 12\times \log_2 x$$ and $$\frac 12\times \log_2 n>\log_2 (\log_2(n-1))$$ at least for $n>11$.