398 | 36 INTRODUCING TURING’S mATHEmATICS
regularity, that there are laws governing their behaviour, and that they obey these laws with
almost military precision.
To see what he meant by this, we’ll consider the prime-counting function p(x), which
counts the number of primes up to any number x. So p(10) = 4, because there are exactly four
primes (2, 3, 5, 7) up to 10, and p(20) = 8, because there are now a further four (11, 13, 17, 19).
Continuing, we find that p(100) = 25, p(1000) = 168, and p(10,000) = 1229.
If we plot the values of the primes up to 100 on a graph we get a jagged pattern—each new
prime creates a jump. But if we stand back and view the primes up to 100,000, we get a lovely
smooth curve—the primes do indeed seem to increase very regularly (Fig. 36.4).
80,000 100,0008000y60,000600040,000400020,0002051015202540 60 80 100 xy2000x figure 36.4 The distribution of the primes.We can describe this regularity more precisely by comparing the values of x and p(x) as x
increases. We get Table 36.1, which lists x, p(x), and their ratio x/p(x).
So up to 100 one-quarter of the numbers are prime, up to 1000 about one-sixth of them are
prime, and so on. We can express this ‘thinning-out’ more precisely by noting that whenever x is
multiplied by 10, the ratio x/p(x) seems to increase by around 2.3. This number 2.3 turns out to
be the natural logarithm of 10, and the natural logarithm function y = ln x turns multiplication
into addition. We can summarize this phenomenon by saying that, as x increases, p(x) behaves
like x/ln x – or, more precisely, that the ratio of p(x) and x/ln x approaches 1 as x becomes large.
This celebrated result is known as the ‘prime number theorem’: the German mathematician Carl
Friedrich Gauss guessed it while experimenting with prime numbers at the age of 15. But it was
not proved until 1896, when the mathematicians Jacques Hadamard (from France) and Charles de
la Vallée Poussin (from Belgium) did so independently, using sophisticated ideas from calculus.