1
$\begingroup$

Let $x$ be greater than or equal to $3$. Prove there are more than $\frac {\ln(\ln(x))}{\ln 2}$ prime numbers $p \leq x$.
Hint: use Euclid's proof and induction.

I have run across this question in a book on L-functions that I am reading. I am only at the beginning of the book and this is the first exercise. So far I have been able to understand everything without difficulty, but I have no idea how I am supposed to approach this problem. If someone can help out I will greatly appreciate it.

$\endgroup$
0
$\begingroup$

$\frac {\ln(\ln(x))}{\ln 2} = \log_2 (\ln x)$

Euclid's proof.

There are infinitely many prime numbers

Proof:

Suppose there are finitely many.

$P={p_1,p_,\cdots,p_n}$ is the set of prime numbers.

Multiply together all the elements in P. subtract 1. Either this number is prime. Or it has a prime factor that is not in $P.$

How to apply it to what we have here.

Since each $p_n < x$

If there are $n$ prime numbers less than or equal to $x$

There are at least $n+1$ prime numbers less than or equal to $x^n$

There are $2$ prime numbers less than or equal to $2^2$

$\log_2(\ln(2^2) = \log_2 2 + \log_2 \ln 2\\ \log_2 \ln 2 < 0\\ 1 + \log_2 ln 2 < 2$

There are $3$ at least prime numbers less than or equal to $(2^3)$

$2(2^2) = 2^3$

$\log_2(\ln(2^3)) = \log_2 3 + \log_2\ln 2 < 3 $

I say: There are at least $n$ prime numbers less than or equal to $2^{2^{n}}$

The base case is sufficiently covered.

Suppose for all $k\le n$ there are at least $k$ prime numbers $< 2^{2^{k}}$

Then we must show there are least n+1 prime numbers $< 2^{2^{n+1}}$

If there are exactly $n$ prime numbers numbers $\le 2^{2^{n}}$

Then we can multiply them all all together. There will be a prime number less the product will be less than $\prod_\limits{k=1}^{n} 2^{2^k} = 2^{\sum 2^k} = 2^{2^{n+1}-1}<2^{2^{n+1}}$

There are at least $n+1$ less than $2^{2^{n+1}}$

$\log_2 \ln 2^{2^{n+1}} = (n+1) + \log_2 \ln 2 < n+1$

For any $x\ge 2^2$ there are at least $\log_2 \ln x$ prime numbers less than $x.$

Which still leaves one case left to show $x = 3$

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