0
$\begingroup$

I have been given the following question in my homework:

Show that for every $n \in \mathbb{N}$ there are at least ${\log_2log_2 (n-1)}$ primes in $[1,n]$

I think it is related to euclidean and induction but I am having difficulties developing my solution.

Thanks for your help (:

$\endgroup$
1
$\begingroup$

Euclid's proof that there are infinitely many primes also shows that the $n$-th prime satisfies $p_n\le 2^{2^{n}}$, which also gives $\pi(n)\ge \log_2(\log_2(n-1))$ , see this MSE question.

Remark: We can easily prove a better estimate, using an elementary argument starting with $2^n\le \binom{2n}{n}<4^n$, which gives $$ \pi(n)>\frac{n}{6\log n} $$ for all $n\ge 2$ (see also this MSE question).

$\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.