16
$\begingroup$

Do primes become more or less frequent as you go further out on the number line? That is, are there more or fewer primes between $1$ and $1{,}000{,}000$ than between $1{,}000{,}000$ and $2{,}000{,}000$?

A proof or pointer to a proof would be appreciated.

$\endgroup$
2
  • 4
    $\begingroup$ Yes (as has been answered): the heuristic reason is that we can list the primes $p_1, p_2, \dots$. Each time you apply the sieve of Eratosnese you exclude the numbers divisible by $p_n$ and weed out "$(1-1/p_n)$" of the natural numbers (i.e., asymptotic density). So in the end you are left with $\prod ( 1 - 1/p_n)$ fraction of the natural numbers; since the sum $\sum \frac{1}{p_n} = \infty$, this is the proportion zero. So we should expect the primes to have density zero. $\endgroup$
    – Akhil Mathew
    Commented Jul 21, 2010 at 0:23
  • 2
    $\begingroup$ Check out the Riemann-zeta function if you want something a bit more technical. It gives a pretty precise estimate of the distribution of primes, indirectly. $\endgroup$
    – Noldorin
    Commented Jul 21, 2010 at 7:38

2 Answers 2

Reset to default
20
$\begingroup$

From the Wikipedia article about the prime number theorem:

Roughly speaking, the prime number theorem states that if a random number nearby some large number N is selected, the chance of it being prime is about 1 / ln(N), where ln(N) denotes the natural logarithm of N. For example, near N = 10,000, about one in nine numbers is prime, whereas near N = 1,000,000,000, only one in every 21 numbers is prime. In other words, the average gap between prime numbers near N is roughly ln(N).

$\endgroup$
5
$\begingroup$

The Sieve of Eratosthenes is a very intuitive visual representation of why the frequency of prime numbers goes down as you go further out on the number line.

$\endgroup$
3
  • $\begingroup$ This is really a less detailed version of Akhil's comment. $\endgroup$
    – BBischof
    Commented Jul 21, 2010 at 4:43
  • 3
    $\begingroup$ @BBischof Akhil's comment derives the answer to this question with mathematical rigor. My answer offers a link to a visual representation of the trend for the sake of gaining intuition. Its nice to have both the proof of the result and intuition about the result. $\endgroup$
    – Ami
    Commented Jul 21, 2010 at 5:01
  • $\begingroup$ Agreed @Ami, it is a useful answer if not as rigorous. $\endgroup$
    – dsolimano
    Commented Jul 21, 2010 at 13:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .