The Mathematical Experience 
by Philip J Davis & Reuben Hersh 
5.The Prime Number Theorem (p209)
THE THEORY of numbers is simultaneously one of the most elementary branches
of mathematics in that it deals, essentially, with the arithmetic properties
of the integers 1, 2, 3,. . . and one of the most difficult branches insofar
as it is laden with difficult problems and difficult technique.
Among the advanced topics in theory of numbers, three may be selected as
particularly noteworthy: the theory of partitions,
Fermat's "Last
Theorem," and the prime number theorem. The theory of partitions concerns
itself with the number of ways in which a number may be broken up into smaller
numbers. Thus, including the "null" partition, two may be broken up as 2
or 1 + 1. Three may be broken up as 3, 2 + 1, 1 + 1 + 1, four may be broken
up as 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1. The number of ways that
a given number may be broken up is far from a simple matter, and has been
the object of study since the midseventeen hundreds. The reader might like
to experiment and see whether he can systematize the process and verify that
the number 10 can be broken up in 42 different ways.
Pierre de Fermat 1601  1665 
Fermat's "Last Theorem" asserts that if n > 2, the equation
x^{n} + y^{n} =
z^{n} cannot be solved in integers x, y, z, with xyz
¹ 0. This theorem
has been proved (1979) for all n < 30,000, but the general theorem
is remarkably elusive. Due to the peculiar history of this problem, it has
attracted more than its share of mathematical crackpottery and most
mathematicians ardently wish that the problem would be settled. The prime
number theorem, which is the subject of this section, has great attractions
and mystery and is related to some of the central objects of mathematical
analysis. It is also related to what is probably the most famous of the unsolved
mathematical problemsthe socalled
Riemann
Hypothesis. It is one of the finest examples of
the extraction of order from chaos in the whole of mathematics.
Soon after a child learns to multiply and divide, he notices that some numbers
are special. When a number is factored, it is decomposed into its basic
constituentsits prime factors. Thus, 6 = 2 x 3, 28 = 2 x 2 x 7, 270 = 2
x 3 x 3 x 3 x 5 and these decompositions cannot be carried further. The numbers
2, 3, 5, 7,. . . are the prime numbers, numbers that cannot themselves be
split into further multiplications. Among the integers, the prime numbers
play a role that is analogous to the elements of chemistry.
Table of primes (Click to Expand) 
Let us make a list of the first few prime numbers: 2 3 5 7 11 13 17 19 23
29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109113 ......
This list never ends. Euclid already had proved
that there are an infinite number of primes. Euclid's proof is easy and elegant
and we will give it. Suppose we have a complete list of all the prime numbers
up to a certain prime Pm. Consider the integer N = (2
^{.} 3 ^{.} 5 ^{.}
^{.} ^{.} Pm) + 1, formed by adding
1 to the product of all the primes up to Pm. Now N is larger than
Pm (for it is certainly more than twice its size). When N is divided
by 2 it goes 3 ^{.} 5 ^{.}
^{.} ^{.} Pm times and leaves a remainder
1. When it is divided by 3, it goes 2 ^{.} 5
^{.} ^{.} ^{.} Pm and
leaves a remainder 1. Similarly, it leaves a remainder of 1 when divided
by any of the primes 2, 3,5,. ...Pm.
Now N is either a prime number or it isn't. If it is a prime number,
it is a prime number greater than Pm. If it isn't a prime number,
it may be factored into prime numbers. But none of its prime factors can
be 2, 3, 5,. ...., Pm as we just saw. Therefore there is a prime number
greater than Pm. The logical argument (actually, the dilemma, which
forces one to the same conclusion whichever path one is compelled to take)
tells us that the list of primes never ends.
The second feature of the list of primes that strikes one is the absence
of any noticeable pattern or regularity. Of course all the prime numbers
except 2 are odd, so the gap between any two successive primes has to be
an even number. But there seems to be no rhyme or reason as to which even
number it happens to be. There are nine prime numbers between 9,999,900 and
10,000,000:
9,999,901  9,999,907  9,999,929  9,999,931 
9,999,937  9,999,943  9,999,971  9,999,973 
9,999,991. 
But among the next hundred integers, from 10,000,000 to 10,000,100, there
are only two: 10,000,019 and 10,000,079.
"Upon looking at these numbers, one has the feeling of being in the presence
of one of the inexplicable secrets of creation," writes Don Zagier in an
outburst of modern number mysticism. What is known about primes and what
is not known or conjectural would fill a large book. Here are some samples.
The largest known prime in 1979 was 2^{21,701} 1. There is a prime
between n and 2n for every integer n > 1. Is there
a prime between n ^{2} and (n + 1)^{2} for
every n > 0? No one knows. Are there an infinity of primes of the
form n ^{2 }+ 1 where n is an integer? No one knows.
There are runs of integers of arbitrary length which are free of primes.
No polynomial with integer coefficients can take on only prime values at
the integers. There is an irrational number A such that
[_{A}3^{n }] takes on only prime values as n =
0, 1, 2 (Here the notation [x] means the greatest integer
£ x.) Is every even number the sum
of two odd primes? No one knows; this is the notorious
Goldbach conjecture. Are there an infinite
number of prime pairs, such as 1; 3 or 17;19 or 10,006,427;10,006,429 which
differ by 2? This is the problem of the twin primes, and no one knows the
answer though most mathematicians are convinced that the statement is very
likely to be true. Some order begins to emerge
from this chaos when the primes are considered not in their individuality
but in the aggregate; one considers the social statistics of the primes and
not the eccentricities of the individuals. One first makes a large tabulation
of primes. This is difficult and tedious with pencil and paper, but with
a modern computer it is easy. Then one counts them to see how many there
are up to a given point. The function
p(n) is defined as the number of primes
less than or equal to the number n. The function
p(n) measures the distribution of the prime
numbers. Having obtained it, it is only natural to compute the ratio
n/p(n) which tells us what fraction
of the numbers up to a given point are primes. (Actually, it is the reciprocal
of this fraction.) Here is the result of a recent computation.
n 
p(n) 
n/p(n) 
10  4  2.5 
100  25  4.0 
1000  168  6.0 
10,000  1,229  8.1 
100,000  9,592  10.4 
1,000,000  78,498  12.7 
10,000,000  664,579  15.0 
100,000,000  5,761,455  17.4 
1,000,000,000  50,847,534  19.7 
10,000,000,000  455,052,512  22.0 
Notice that as one moves from one power of 10 to the next, the ratio
n/p(n) increases by roughly 2.3.
(For example, 22.0  19.7 = 2.3.) At this point, any mathematician worth
his salt thinks of log_{e} 10 (=2.30258...) and on the basis
of this evidence, it is easy to formulate the conjecture that
p(n) is approximately equal
to n/log n.
The more formal statement that
lim_{n®¥
}p(n)/(n/log n) = 1

Carl Friedrich Gauss 1777  1855 

Jacques Hadamard 1865  1963 
is the famous prime number theorem. The discovery of the theorem can be traced
as far back as Gauss, at age fifteen (around 1792), but the rigorous mathematical
proof dates from 1896 and the independent work of C. de la Vallee Poussin
and Jacques Hadamard. Here is order extracted from confusion, providing
a moral lesson on how individual eccentricities can exist side by side with
law and order.
While the expression n/log n is a fairly simple approximation
for p(n) , it is not terribly close, and
mathematicians have been interested in improving it. Of course, one does
this at the price of complicating the approximant. One of the most satisfactory
approximants to p(n) is the function
R(n) = 1 +
å^{¥}_{k=1
}1/_{kz(k+1) }(log
n)^{k} /_{k!}
where z(z) designates the celebrated Riemann
zeta function :
z(z) = 1 + 1/2^{z }+ 1/3^{z
}+ 1/4^{z }+ ....
The accompanying table shows what a remarkably good approximation
R(n) is to p(n) :

p(n) 
R(n) 
100,000,000  5,761,455  5,761,552 
200,000,000  11,078,937  11,079,090 
300,000,000  16,252,325  16,252,355 
400,000,000  21,336,326  21,336,185 
500,000,000  26,355,867  26,355,517 
600,000,000  31,324,703  31,324,622 
700,000,000  36,252,931  36,252,719 
800,000,000  41,146,179  41,146,248 
900,000,000  46,009,215  46,009,949 
1,000,000,000  50,847,534  50,847,455 
Let us turn, finally, to the question of twin prime pairs. It is thought
that there are an infinite number of such pairs, though this is still an
open question.
Why do we believe it is true, even though there is no proof? First
of all, there is numerical evidence; we find more prime pairs whenever we
look for them; there does not seem to be a region of the natural number system
so remote that it lies beyond the largest prime pair. But more than that,
we have an idea how many prime pairs there are. We can get this idea
by noticing that the occurrence of prime pairs in a table of prime numbers
seem to be unpredictable or random. This
suggests the conjecture that the chance of two numbers n and n
+ 2, both being prime, acts like the chance of getting a head on two
successive tosses of a coin. If two successive
random experiments are independent, the chance of success on both is the
product of the chances of success on either; for example, if one coin has
probability ^{1}/_{2} of coming up heads, two coins have
probability ^{1}/_{2} x ^{1}/_{2} =
^{1}/_{4 }of coming up a pair of heads.
Now the prime number theorem, which has been proved, says that if n is
a large number, and we choose a number x
at random between 0 and n, the chance that x is 1 prime will
be "about" 1/log n. The bigger n is, the better is the
approximation given by 1/log n to the proportion of primes in
the numbers up to n.
If we trust our feeling that the occurrence of twin primes is like two coins
coming up heads, then the chance 1 that both x and x + 2 are
prime would be about 1/(log n)^{2}. In other words, there
would be about n/(log n)^{2} prime pairs to be found
between 0 and n. This fraction approaches infinity as n goes
to infinity, so this would provide a quantitative version of the prime pair
conjecture.
For reasons involving the dependence of x + 2 being prime on the
supposition that x is already prime, one should modify the estimate
n/(log n)^{2} to (1.32032..)n/(log
n)^{2}.
Appended is a comparison between what has been found and what is predicted
by this simple formula. The agreement is remarkably good, but the final Q.E.D.
is yet to be written.
Interval 
Prime twins 
Prime twins 
100,000,000  100,150,000  584  601 
1,000,000,000  1,000,150,000  461  466 
10,000,000,000 10,000,150,000  374  389 
100,000,000,000  100,000,150,000  309  276 
1,000,000,000,000  1,000,000,150,000  259  276 
10,000,000,000,000  10,000,000,150,000  221  208 
100,000,000,000,000  100,000,000,150,000  191  186 
1,000,000,000,000,000  1,000,000,000,150,000  166  161 
Further Readings. 
Chaos  Quantum  Logic  Cosmos  Conscious  Belief  Elect.  Art  Chem.  Maths 