Percentage of primes among the natural numbers

Solution 1:

People are quoting the Prime Number Theorem here, but that is pretty serious overkill. Even Chebyshev's theorem is a level above, in my opinion.

In my undergraduate number theory course, I prove that the prime numbers have density zero in the positive integers (including a careful statement of what this means). The proof is given as Theorem 6 in these notes (Wayback Machine). In fact it builds on the OP's observation that the density must be at most $\frac{1}{2}$ because half of all numbers are divisible by $2$. Similarly the density must be at most $\frac{1}{3}$ because every prime number $p > 5$ is relatively prime to $6$, and $\frac{\varphi(6)}{6} = \frac{1}{3}$. One can get a complete proof by showing that for each $\epsilon > 0$, there exists a positive integer $d$ such that $\frac{\varphi(d)}{d} < \epsilon$. This was proved earlier in the course: it is Proposition 6 in this set of notes (Wayback Machine). The proof doesn't use any analytic fact deeper than the divergence of the harmonic series.

Solution 2:

I will denote the set of all primes by $\mathbb P$.

It is not exactly clear what one can understand under percentage of primes, but one possible interpretation is the limit $$\lim\limits_{n\to\infty} \frac{\pi(n)}n = \lim\limits_{n\to\infty} \frac{|\{p\in\mathbb P; p\le n\}|}n$$ of the ratio of primes and all numbers in the interval $[1,n]$. This is precisely the asymptotic density of the set $\mathbb P$ and using Prime number theorem one can show that it is equal to zero.

The asymptotic density of the set $A$ is defined as $$d(A)=\lim\limits_{n\to\infty} \frac{|\{a\in A; a\le n\}|}n.$$ A possible way to show $d(\mathbb P)=0$ without using PNT is to use the result from the paper Ivan Niven. The asymptotic density of sequences. Bull. Amer. Math. Soc., 57(6):420-434, 1951.

Corollary 1. If for a set of primes $\{p_i\}$ we have $d(A_{p_i})=0$ for every $i$, and if $\sum p_i^{-1}=\infty$ then $d(A)=0$.

Here, for any $A\subseteq\mathbb N$ and a prime $p$, the set $A_p$ is defined as $$A_p=\{n\in A; p\mid n, p^2\nmid n\}.$$

Applying the above result with $A=\mathbb P$ and $\{p_i\}=\mathbb P$ gives $d(\mathbb P)=0$.

We are using the fact that $\sum_{p\in\mathbb P} \frac1p=\infty$. A very nice proof of this fact was given by Erdős, see Proofs from The Book by Martin Aigner, Günter M. Ziegler p.5.

Another short proof of $d(\mathbb P)=0$ is given in this paper:

S. E. Mamangakis. Shorter notes: Remark on $\pi(x) = o(x)$. Proc. Amer. Math. Soc., 13(4):664--665, 1962

Solution 3:

According to the Prime Number Theorem $$ \lim_{n\to\infty}\frac{\pi(n)}{n/\log(n)}=1\tag{1} $$ where $\pi(n)$ is the number of primes less than or equal to $n$. Therefore, there is an $N$ so that if $n\ge N$, $$ \frac{\pi(n)}{n}\le\frac{2}{\log(n)}\tag{2} $$ Since there are infinitely many primes and infinitely many positive integers, there is no way to divide the number of primes by the number of positive integers to get a proportion. The next best attempt at a proportion would be the limit of the proportion in $[1,n]$: $$ \lim_{n\to\infty}\frac{\pi(n)}{n}\tag{3} $$ Inequality $(2)$ says that the limit in $(3)$ is $0$.

Addendum:

Pete Clark mentions that the Prime Number Theorem is overkill for this question, and I agree. In light of this, let's consider first the density of positive integers not divisible by a particular prime $p$. Define $$ F_p=\{n\in\mathbb{Z}^+:p\nmid n\}\tag{4} $$ It is pretty clear that $$ \lim_{n\to\infty}\frac{|F_p\cap[1,n]|}{n}=1-\frac{1}{p}\tag{5} $$ Divisibility by a prime $p$ and a prime $q$ are independent; that is, $p\mid n$ and $q\mid n$ if and only if $pq\mid n$. Thus, the density of $F_p\cap F_q$ is $$ \lim_{n\to\infty}\frac{|F_p\cap F_q\cap[1,n]|}{n}=\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\tag{6} $$ Continuing in this manner, we get that the density of positive integers not divisible by any in a set of the primes $\{p_i\}_{i=1}^k$ would be $$ \lim_{n\to\infty}\frac{|\bigcap_{i=1}^kF_{p_i}\cap[1,n]|}{n}=\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)\tag{7} $$ Therefore, the density of the primes not in $\{p_i\}_{i=1}^k$ is no greater than $\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$. Since the density of primes in $\{p_i\}_{i=1}^k$ is $0$, the density of all primes is no greater than $\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$.

If we enumerate all primes as $\{p_i\}_{i=1}^\infty$, using the Fundamental Theorem of Arithmetic, we get that $$ \begin{align} \frac{1}{\prod_{i=1}^\infty\left(1-\frac{1}{p_i^\alpha}\right)} &=\prod_{i=1}^\infty\left(1+\frac{1}{p_i^\alpha}+\frac{1}{p_i^{2\alpha}}+\cdots\right)\\ &=\sum_{k=1}^\infty\frac{1}{k^\alpha}\tag{8} \end{align} $$ As Pete mentions, since the harmonic series diverges, as $\alpha\to1^+$, $(8)$ implies that $$ \prod_{i=1}^\infty\left(1-\frac{1}{p_i}\right)=0\tag{9} $$ Thus, the density of primes is $0$.

Solution 4:

Almost all of the natural numbers are composite; that is, the percentage of primes in $\mathbb{N}$ is $0$.

We know that the number of primes less than or equal to a natural number $x$ is asymptotic to $x/\log(x)$; that is, it has the same behavior for large $x$. Since this grows strictly slower than $x$, we see that the proportion of primes goes to $0$.

From this formula, we can also find that the proportion of primes in the natural numbers less than $x$ is $1/\log(x)$.