In the previous post we discussed the number of primes less than a given number and derived some very poor estimates for this quantity. In this post, using no extra technical machinery whatsoever, we derive a slightly better estimate.

Previously, we used Euclid’s proof of the infinitude of the primes as inspiration for a way of arriving at an upper bound for the number of primes less than a given number. Here, we will come up with a slightly cleverer, more quantitative proof of Euclid’s Theorem and, as before, our estimate will grow out of the proof of Euclid’s Theorem, the improvement in the bound being testament to the fact that the proof is more illuminating.

In Euclid’s proof, one constructs a number which is not divisible by any of the first n primes, but in fact it is clear we are done if we prove the existence of a number that has a prime factor not among the first n primes. To do this we need to show that it cannot be the case that every number has all of its prime factors among the first n primes. And, luckily, it does indeed seem very unlikely that every number has all of its prime factors among the first n primes. So the quantitative question we ask is: “How many numbers less than or equal to x have all of their prime factors among the first n primes?”. Call this number $N(x).$

### Reductio

Let’s estimate $N(x)$: Let k be some number less than or equal to x, all of whose prime factors are among the first n primes. We can write

$k = k_1^2m$,

where m is square-free, that is it is not divisible by the square of any prime, and where $k_1 \leq \sqrt{k} \leq \sqrt{x}$. The question is: “How many such numbers are there?”. We can get away with a crude estimate obtained by counting the two factors entirely independently: Firstly, there are at most $\sqrt{x}$ choices for $k_1$ simply because it is less than $\sqrt{x}$. What about m? Well, we know that m must be a product of primes (this follows from the fact that every number is divisible by a prime – see the previous post) and that all its prime factors are among the first n primes so

$m = p_1^{\alpha_1}\cdot\dots \cdot p_n^{\alpha_n}$,

where, since m is not divisible by the square of any prime, each exponent $\alpha_j$ is either equal to one or equal to zero. Counting all possible choices of these exponents tells us there are at most $2^n$ possible values of m. This counting work tells us that $N(x) \leq 2^n\sqrt{x}$.

If we assume for the sake of contraction that there are only n primes, then $N(x) = x-1$ for every x, because every number (except one) has a prime divisor and therefore every number (except one) has a prime divisor among the first n primes. This would mean that $x-1 \leq 2^n\sqrt{x}$ for every $x$, which is clearly nonsense. Therefore, there are infinitely many primes.

### An Estimate and a Sum

As promised, we use the simple idea of this proof to get an estimate on the number of primes less than a given number. Fix $x$ and write $n = \pi(x)$. This means we are calling the biggest prime less than or equal to $x$ the $n^{th}$ prime. So the first $n$ primes are actually all the primes less than or equal to x. Thus $N(x)$ is counting the number of numbers less than or equal to $x$ all of whose prime factors are less than or equal to x. On the one hand this is obviously equal to $x -1$, but on the other hand we have the bound obtained in the previous section, i.e.$N(x) \leq 2^{\pi(x)}\sqrt{x}$, and so $x-1 \leq 2^{\pi(x)}\sqrt{x}$. We can deduce from this that

$\pi(x) \geq C\log x$.

While this is a bit of an improvement on $\log \log x$, it is still very bad. For example, it says that the number of primes less than one billion is greater than 14.9 when in actual fact it is greater than fifty million.

Another thing that comes out of the work in this post is a very quick and neat proof that the sum of the reciprocals of the prime nunbers diverges, i.e. this sum:

$\sum_{p\ \text{prime}}\frac{1}{p}$.

Our observation is the following one: For any prime number $p$, only every $p^{th}$ number is divisible by $p$. Therefore the number of numbers less than or equal to $x$ which are divisible by a given prime $p$ is at most $x/p$. We use this observation in the context of the quantity $x - N(x)$. This is the number of numbers less than or equal to $x$ which have a prime divisor greater than $p_n$, i.e. which are divisible by one or more of $p_{n+1},\ p_{n+2},\ ...$. This is not more than

$\frac{x}{p_{n+1}} + \frac{x}{p_{n+2}} + \frac{x}{p_{n+3}} + ...$

If the sum $\sum_{p\ \text{prime}}\frac{1}{p}$ converged, then the tail of the sum could be made arbitrarily small and so by choice of n, we would have that

$\frac{x}{p_{n+1}} + \frac{x}{p_{n+2}} + \frac{x}{p_{n+3}} + ... < \frac{x}{2}.$

Thus $x - N(x) \leq x/2$, or $x/2 \leq N(x)$ which is clearly nonsense again. Therefore the sum diverges.