Frequency of Primes

Date: 03/17/97 at 21:34:55
From: Jonah Knobler
Subject: Frequency of Primes

I am a student in an Algebra II class, and I'm wondering about 
number theory.

I know what a prime number is, and I believe there are an infinite 
number of them (someone HAS proved this, right?)

Is there any discernible pattern in the frequency of prime numbers? 
For instance, the distance between primes starts as:

1 (2->3)
2 (3->5)
2 (5->7)
4 (7->11)
2 (11->13)
4 (13->17)
2 (17->19)
4 (19->23)
6 (23->29)
2 (29->31).

This sequence seems to have no pattern, but it is only a VERY small 
part of the sequence.  My question is this: knowing that, as you 
continue toward greater primes, the distance between primes (usually) 
increases, is there a general trend in HOW this distance increases?  
Does it approximately follow a quadratic/logarithmic/linear/whatever 
function?  Is it completely random?  What does it look like on a 
graph?

Seeing how important prime numbers are in number theory, I would 
assume that discovering an interesting number or formula popping up 
here (e.g. pi, e, etc.) would be fascinating.  

Thanks!

- Jonah Knobler

Date: 03/18/97 at 08:51:06
From: Doctor Rob
Subject: Re: Frequency of Primes

The Proof of the Infinite Number of Primes:

This was done by Euclid more than 2000 years ago. He used a proof by 
contradiction.  

Suppose p(1), ..., p(n) is a list of all the prime numbers, i.e., that 
there are only finitely many.  Then construct the number 

 N = p(1)*p(2)*...*p(n) + 1.  

By the Fundamental Theorem of Arithmetic, this can be uniquely written 
as a product of prime numbers.  If p(i) is one of those prime numbers, 
then N = p(i)*M, and so:

 1 = N - p(1)*...*p(n) = p(i)*[M - p(1)*...*p(i-1)*p(i+1)*...*p(n)],

which demonstrates that p(i) is a prime divisor of 1.  This is, of
course, impossible, since p(i) > 1. Thus none of the prime divisors
of N appears in the list of primes. This contradicts the assumption
that the list contained all primes. The conclusion is that no such
list is complete, and the number of primes must be infinite.


Is there a pattern for the distribution of prime numbers?

This is a problem which has interested number theorists for several
centuries.  There is no discernible pattern known.  Even such simple
questions as, "Does 2 appear infinitely often?" are unresolved.  This
particular question is known as the "Twin Prime Conjecture."  Some
facts are known, however.  For example, it is known that there is an
infinite subsequence {x(n): n=1, 2, ...} of the prime numbers such 
that

  [x(2*n) - x(2*n-1)]/log_e[x(2*n)]

is unbounded (gets bigger than any number you pick in advance).  This
(and more) was proved by Paul Erdos in 1949.

>Seeing how important prime numbers are in number theory, I would 
>assume that discovering an interesting number or formula popping up 
>here (e.g. pi, e, etc.) would be fascinating.  

Yes, wouldn't it.  Notice the appearance of e in the previous 
paragraph! Pi, e, and Euler's constant gamma frequently do appear in 
formulae or theorems involving prime numbers.  For example, there is a 
theorem which says that if you pick two integers at random (in some 
sense which I won't go into), that the probability that they have no 
common prime divisor is 6/pi^2 ~=~ 0.6079271, which I think is really 
pretty!

These are important and interesting questions in number theory, many
of which are unsolved.  It is heartening to see an Algebra II student
with interest in them.  Keep up the good questions!

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/