Notes

Section 4: The Sequence of Primes

Results about primes

Prime[n] is given approximately by n Log[n] + n Log[Log[n]]. (Prime[10^9] is 22,801,763,489 while the approximation gives 2.38 × 10^10.) A first approximation to PrimePi[n] is n/Log[n]. A somewhat better approximation is LogIntegral[n], equal to Integrate[1/Log[t], {t, 2, n}]. This was found empirically by Carl Friedrich Gauss in 1792, based on looking at a table of primes. (PrimePi[10^9] is 50,847,534 while LogIntegral[10^9] is about 50,849,235.) A still better approximation is obtained by subtracting Sum[LogIntegral[n^ri], {i, -∞,∞}] where the ri are the complex zeros of the Riemann zeta function Zeta[s], discussed on page 918. According to the Riemann Hypothesis, the difference between PrimePi[n] and LogIntegral[n] is of order Sqrt[n] Log[n]. More refined analytical estimates of PrimePi[n] are good enough that they are used by Mathematica to compute Prime[n] for large n.

It is known that the ratio of the number of primes of the form 4k+1 and 4k+3 asymptotically approaches 1, but almost nothing has been proved about the fluctuations.

The gap between successive primes Prime[n] - Prime[n-1] is thought to grow on average at most like Log[Prime[n]]^2. It is known that for sufficiently large n a gap of any size must exist. It is believed but not proved that there are an infinite number of "twin primes" with a gap of exactly 2.

From Stephen Wolfram: A New Kind of Science [citation]