The Distribution of the Primes
This unit measures how the primes thin out. It compares the counts of primes up to ten billion with the guesses of Gauss and Legendre, defines the O notation, and proves with one binomial coefficient and Legendre's formula that pi(x) lies between two fixed multiples of x/ln x and that a prime always lies between n and 2n. It introduces the Chebyshev functions, proves the first of Mertens' theorems on sums over primes, shows what a random model of the primes predicts and where arithmetic corrects it, and ends with two races: the primes 4k + 3 against the primes 4k + 1, and pi(x) against li(x), where the leader changes only beyond 10^316.
Below one million there are \(78{,}498\) primes, and below ten billion there are \(455{,}052{,}511\). Unit 8 stated the prime number theorem, which says that these counts behave like \(x/\ln x\), and reported that the theorem was proved in 1896 with tools beyond the Foundation masterclass. This unit shows how much of the truth can be reached with the integers alone: that \(\pi(x)\) lies between two fixed multiples of \(x/\ln x\), that a prime always sits between \(n\) and \(2n\), how fast the sum of \(1/p\) grows, what a random model of the primes predicts and where it fails, and why the primes \(4k + 3\) stay ahead of the primes \(4k + 1\) almost all the time.
1 Counting the primes
Unit 8 told how Carl Friedrich Gauss (1777-1855) counted primes in blocks of a thousand at the age of fifteen and guessed that near a number \(t\) about one integer in \(\ln t\) is prime, and how Adrien-Marie Legendre (1752-1833) published an empirical formula of the same kind in 1798. Both guesses concern the prime counting function \(\pi(x)\), the number of primes \(p \le x\), where \(x\) is any real number and \(\ln\) the natural logarithm. If Gauss’s guess is added up over every \(t\) from \(2\) to \(x\) and the sum is replaced by an integral, the result is the logarithmic integral \begin{equation} \operatorname{li}(x) = \int_{2}^{x} \frac{\dd t}{\ln t} , \label{eq:li} \end{equation} the area under the curve \(1/\ln t\) from \(2\) to \(x\). Some tables start the integral at \(0\) instead of \(2\), which adds \(1.045\) to every value but needs a convention at \(t = 1\), where \(1/\ln t\) is infinite; this unit uses the integral from \(2\) throughout and avoids the question. Table 1 compares both guesses with the truth for the first ten powers of ten.