Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How high is the percentage of primes in $\mathbb{N}$?

($\mathbb{N} := \lbrace { 1, 2, 3, \ldots \rbrace }$ ; a prime is only divisible by itself and 1 in $\mathbb{N}$)

The percentage has to be lower than 50% as all even numbers (except for 2) aren't primes. So the percentage has to be lower than $1 - (\frac{1}{2} + (\frac{1}{3} - \frac{1}{6})) = 1 - (\frac{1}{2} + \frac{1}{6}) = 1 - (\frac{1}{2} + \frac{1}{2 \cdot 3}) = \frac{1}{3}$

I guess it will be something like that:

$$\frac{\text{primes in } \mathbb{N}}{\text{numbers in } \mathbb{N}} = 1 - \sum_{i=\text{first Prime}}^\text{primes} \frac{1}{\prod_{j=\text{first prime}}^{i\text{-th prime}} j}$$

But calculating this (exact) value goes definitely beyond my math skills. Can somebody help me?

share|improve this question
2  
google "prime number theorem". And, it is, indeed, deep. –  David Mitra Nov 14 '11 at 18:41
3  
@David In fact, the weaker result of Chebyshev that $c \frac{x}{\log x} \leqslant \pi(x) \leqslant C \frac{x}{\log x}$ (for constants $0 < c < C < \infty$) already tells that the primes have zero natural density among $\mathbb N$. This result is, of course, very non-trivial, but not too deep; I think the sieve methods are good enough to get it. I don't think that the OP is asking about the precise asymptotics of the density... –  Srivatsan Nov 14 '11 at 18:44
10  
The fact that $\lim_{n \to \infty} \dfrac{\text{primes } \leq n}{n} = 0$ is much easier to derive than the prime number theorem, or even Chebyshev's estimates. The OP is on the right track with his computions for sieving out $2$ and $3$. –  Matt E Nov 14 '11 at 19:07
1  
@moose: Your estimate, which I interpret as $1-\left(\frac{1}{2}+\frac{1}{6}+\frac{1}{30}+\frac{1}{210}+\cdots\right)$ gives a positive density, which is not right. Maybe observe that the fraction taken care of by $2$, $3$, and $5$ is actually $(1-1/2)(1-1/3)(1-1/5)$, which is $11/15$, while your $1/2+1/6+1/30$ is $21/30$. –  André Nicolas Nov 14 '11 at 19:07
2  
@moose: I am not sure that there is some consensus about how long to wait before accepting an answer (see meta.math.stackexchange.com/questions/2553/…), but I think that you've accepted to soon. The answer by Pete Clark is beautiful and the proof he suggests is really elementary (at least in comparison with the proofs suggested in other answers so far). –  Martin Sleziak Nov 14 '11 at 19:51
show 4 more comments

5 Answers

up vote 15 down vote accepted

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})$ 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

share|improve this answer
    
how does that theorem help us? the sum of reciprocals of primes diverges. –  smackcrane Nov 14 '11 at 18:53
    
Thanks @smackcrane, I removed the theorem. –  Martin Sleziak Nov 14 '11 at 18:57
add comment

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. 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. The proof doesn't use any analytic fact deeper than the divergence of the harmonic series.

share|improve this answer
3  
A little note: This approach gives an upper bound of $O(\frac{x}{\log \log x})$ on the number of primes not exceeding $x$ (as mentioned in the linked notes after Theorem 6 :)). –  Srivatsan Nov 14 '11 at 19:41
3  
Dear Pete, I agree that this is the natural proof of the density statement that the OP is asking about. Regards, –  Matt E Nov 14 '11 at 20:39
    
I hope that I didn't just reproduce something in my addendum that was in one of your links. I scanned the link contents, but I might have missed something. –  robjohn Nov 15 '11 at 18:15
add comment

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\!\!\!\not|\;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|n$ and $q|n$ if and only if $pq|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{|\cap_{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}}+\dots\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$.

share|improve this answer
add comment

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

share|improve this answer
add comment

Better aproximation than $\frac{1}{3}$:

$\frac{6}{10} \Rightarrow \frac{3}{5} < $ non-prime numbers

$\frac{4}{10} \Rightarrow \frac{2}{5} >$ prime numbers

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.