How many primes are there below x?
Tonight's idea
Write \(\pi(x)\) for the number of primes up to \(x\). It is just the letter, nothing to do with circles. From the sieve (grade 6, b1): \(\pi(10) = 4\), \(\pi(100) = 25\), \(\pi(1000) = 168\). The primes thin out. How fast?
Gauss, as a teenager with a printed table of primes, counted how many fell in each block of a thousand and noticed that near \(x\) the density was about \(1/\ln x\): roughly one integer in every \(\ln x\) is prime. Adding up that density from \(2\) to \(x\) gives the guess
\[\pi(x) \approx \operatorname{Li}(x) = \int_2^x \frac{dt}{\ln t}, \qquad \text{and more crudely} \qquad \pi(x) \approx \frac{x}{\ln x}.\]
Gauss never published it. The statement
\(\dfrac{\pi(x)}{x/\ln x} \to 1\) as \(x \to \infty\) (the prime number theorem)
was proved only in 1896, by Hadamard and de la Vallée Poussin independently, using complex analysis. Read the arrow carefully (b1). It says the ratio tends to \(1\), not that the difference shrinks: \(\pi(x) - x/\ln x\) grows without bound. And \(\operatorname{Li}(x)\) is the far better estimate.
Watch one: the table
| \(x\) | \(\pi(x)\) | \(x/\ln x\) | \(\operatorname{Li}(x)\) | \(\pi(x) \div \frac{x}{\ln x}\) | \(\pi(x) \div \operatorname{Li}(x)\) |
|---|---|---|---|---|---|
| \(10^2\) | 25 | 21.7 | 29.1 | 1.151 | 0.860 |
| \(10^3\) | 168 | 144.8 | 176.6 | 1.161 | 0.951 |
| \(10^4\) | 1,229 | 1,085.7 | 1,245.1 | 1.132 | 0.987 |
| \(10^5\) | 9,592 | 8,685.9 | 9,628.8 | 1.104 | 0.996 |
| \(10^6\) | 78,498 | 72,382.4 | 78,626.5 | 1.084 | 0.998 |
Counts are exact, estimates to one decimal place. By a million the crude ratio is still \(8\%\) high; the \(\operatorname{Li}\) ratio is within a fifth of a percent. \(\operatorname{Li}(x)\) overestimates in every row; it does not always, but the first failure is astronomically far out.
Your turn
- List the primes below \(50\) and count them. Compare with \(50/\ln 50\). Is the ratio above \(1\), like every row of the table?
- (a) Using \(\pi(10^4) = 1229\), compute \(\pi(x) \div (x/\ln x)\) and check it against the table. (b) The differences \(\pi(x) - x/\ln x\) down the table are \(3.3\), \(23.2\), \(143.3\), \(906.1\), \(6115.6\): growing. Explain how the ratio can tend to \(1\) while the difference grows without bound.
- Estimate the number of primes between \(10^6\) and \(2 \times 10^6\): (a) as \(\frac{2 \times 10^6}{\ln(2 \times 10^6)} - \frac{10^6}{\ln 10^6}\); (b) by treating the density as the constant \(1/\ln(1.5 \times 10^6)\) across the whole interval. The true count is \(70{,}435\). Which estimate is closer, and why?
- A \(100\)-digit number is picked at random. Using the density \(1/\ln x\) with \(x = 10^{100}\), estimate the chance it is prime. If only odd numbers are picked, how does the chance change? About how many random odd \(100\)-digit numbers must be tested to expect one prime? Why does RSA need this to be a small number?
Stretch: the \(n\)th prime
If \(\pi(x) \approx x/\ln x\), then the \(n\)th prime \(p_n\) is roughly the \(x\) with \(x/\ln x = n\), and a first try is \(p_n \approx n \ln n\). Test it on \(p_{1000} = 7919\). Then try the refinement \(n(\ln n + \ln \ln n)\) on \(p_{1000}\) and on \(p_{10^6} = 15{,}485{,}863\). Which side of the truth does each land on?
Answers
- \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47\): fifteen primes. \(50/\ln 50 = 12.78\), ratio \(1.17\), above \(1\) as usual.
- (a) \(10^4/\ln 10^4 = 10^4/9.2103 = 1085.7\), ratio \(1229/1085.7 = 1.132\). (b) The ratio tending to \(1\) means the difference is small compared with \(x/\ln x\): \(\dfrac{\pi(x) - x/\ln x}{x/\ln x} \to 0\). A difference of \(6116\) is \(8\%\) of \(72{,}382\); as \(x\) grows the percentage shrinks even though the absolute gap grows. Compare \(x^2 + x\) and \(x^2\): ratio \(\to 1\), difference \(\to \infty\).
- (a) \(\dfrac{2 \times 10^6}{14.5087} - \dfrac{10^6}{13.8155} = 137{,}848.7 - 72{,}382.4 = 65{,}466\). (b) \(\dfrac{10^6}{\ln(1.5 \times 10^6)} = \dfrac{10^6}{14.2210} = 70{,}318\). The density estimate (b) is far closer (off by \(0.2\%\) against \(7\%\)), because it uses the local density \(1/\ln x\) directly; (a) inherits the systematic error of \(x/\ln x\) at both ends. (b) is a one-rectangle approximation to \(\operatorname{Li}(2 \times 10^6) - \operatorname{Li}(10^6) = 70{,}427\).
- \(\ln 10^{100} = 100 \ln 10 = 230.3\), so about \(1\) in \(230\). Even numbers above \(2\) are never prime, so restricting to odd numbers doubles the chance: about \(1\) in \(115\). Expect to test about \(115\) odd candidates. RSA needs two fresh primes of this size or larger for every key; if primes were rare there, finding them would take too long, and the test for primality would have to run thousands of times. A few hundred trials is fine.
Stretch. \(1000 \ln 1000 = 6908\), low by \(13\%\) against \(7919\). The refinement gives \(1000(6.908 + 1.933) = 8840\), now \(12\%\) high. For \(n = 10^6\): \(n \ln n = 13{,}815{,}511\) (low by \(11\%\)) and \(n(\ln n + \ln\ln n) = 16{,}441{,}302\) (high by \(6\%\)). The truth sits between the two, and the refinement's percentage error shrinks faster. The exact statement is \(p_n / (n \ln n) \to 1\), the prime number theorem read backwards.