How the primes are spread out
There are infinitely many primes. How many are there up to a million, and how thinly do they spread out?
Where you are 1 in Divisibility and primes
Why this exists
There are infinitely many primes proves that the primes never run out, but its bound p_n \le 2^{2^{n-1}} guarantees only five primes below a million, where there are 78{,}498. The sieve shows the primes thinning out, with runs of composites as long as you like. Neither says how many primes lie up to x, and counting answers that for one x at a time, never for every x.
This lesson gives three answers, each sharper than the last. Euler’s argument shows that the reciprocals of the primes have a divergent sum, so the primes are far more plentiful than the squares. Chebyshev-type bounds trap the count between two constant multiples of x / \ln x. The prime number theorem, stated here and proved in a later course, says the count is asymptotic to x / \ln x itself. All three rest on Every number has exactly one prime factorization.
Definition
For a real number x, \pi(x) is the number of primes p with p \le x. So \pi(10) = 4, \pi(10.5) = 4, and \pi(x) = 0 for x < 2. Here and below a sum or product over p runs over primes only. Chebyshev’s function is
the natural log of the product of the primes up to x.
For a prime p and a positive integer n, v_p(n) is the exponent of p in the prime factorization of n: v_2(40) = 3 and v_3(40) = 0. Unique factorization makes it well defined, and since the factorization of ab is those of a and b put together, v_p(ab) = v_p(a) + v_p(b). Equivalently, v_p(n) is the number of integers k \ge 1 with p^k \mid n.
Two positive functions are asymptotic when their ratio tends to 1: f(x) \sim g(x) means f(x)/g(x) \to 1 as x \to \infty. The relation is symmetric and transitive, since ratios multiply. Asymptotic does not mean close in difference: x^2 + x \sim x^2, yet the two differ by x.
The central binomial coefficients are \binom{2n}{n} (The binomial theorem).
Intuition
The steps come less often as x grows, and the staircase bends down like x / \ln x, a little above it. Their ratio drifts back toward 1 very slowly; at x = 10^6 it is still about 1.08.
One reading: if about x / \ln x of the integers up to x are prime, then near x roughly one integer in \ln x is prime, and neighboring primes are about \ln x apart on average; near 10^6, one in 14. This heuristic is about averages, not any one stretch.
The proofs turn facts about integers into facts about primes. Euler multiplies out \prod (1 - 1/p)^{-1} and finds the harmonic series inside. Chebyshev’s idea reads the primes inside one integer, \binom{2n}{n}: it is about 4^n, yet each prime power dividing it is at most 2n, so it needs many primes; and every prime between n and 2n divides it, so there cannot be too many of those.
Results
Theorem 1 (Legendre’s formula). For every prime p and every positive integer n,
The sum is finite: its terms are 0 once p^k > n.
Theorem 2 (Euler). For every real x \ge 2,
So \displaystyle \frac12 + \frac13 + \frac15 + \frac17 + \cdots diverges. The proof follows Euler’s product idea. In fact \sum_{p \le x} 1/p - \ln \ln x tends to a constant near 0.2615 (Mertens’ theorem, stated without proof; it is proved in analytic number theory).
Lemma 3. For every integer n \ge 1:
- (a) 2^n \le \binom{2n}{n} and \dfrac{4^n}{2n+1} \le \binom{2n}{n} < 4^n;
- (b) for every prime p, p^{v_p(N)} \le 2n, where N = \binom{2n}{n};
- (c) every prime p with n < p \le 2n has v_p(N) = 1.
Theorem 4 (Chebyshev-type bounds). For every real x \ge 2,
Moreover \theta(x) < x \ln 16 for every real x \ge 1, and for every integer n \ge 1,
Bounds of this shape go back to Chebyshev, around 1850; the route through \binom{2n}{n} below is in the same spirit. The constants are far from the best known: for instance \pi(x) > x / \ln x for every x \ge 17 (Rosser and Schoenfeld, 1962; stated without proof).
Theorem 5 (the prime number theorem, stated without proof).
that is, \pi(x) \ln x / x \to 1 as x \to \infty. Equivalently, p_n \sim n \ln n (Example 6 and Exercise 19). Gauss conjectured it from tables of primes; Hadamard and de la Vallée Poussin proved it independently in 1896, using complex analysis and the Riemann zeta function. The proof belongs to a course in analytic number theory.
Bertrand’s postulate (stated without proof). For every integer n \ge 1 there is a prime p with n < p \le 2n. Its proof refines the study of \binom{2n}{n} below.
Why it is true
Proof of Theorem 1. Since v_p turns products into sums,
and v_p(j) counts the k \ge 1 with p^k \mid j. So v_p(n!) counts the pairs (j, k) with 1 \le j \le n, k \ge 1 and p^k \mid j. Count them by k instead. For fixed k the multiples of p^k among 1, \dots, n are p^k, 2p^k, \dots, \lfloor n/p^k \rfloor p^k, so there are \lfloor n/p^k \rfloor of them. \square
Proof of Theorem 2. Let x \ge 2, let p_1, \dots, p_r be the primes up to x, and choose an integer K with 2^K > x. For each p \le x the finite geometric sum satisfies
Multiply these r inequalities between positive numbers. Multiplied out, the left side has one term 1/(p_1^{a_1} \cdots p_r^{a_r}) for each choice of exponents 0 \le a_i \le K. Every integer n with 1 \le n \le x is one of these denominators: its prime factors are at most n \le x, and each exponent is at most \log_2 n < K. All terms are positive, so
With N = \lfloor x \rfloor, 1/n \ge 1/t for n \le t \le n + 1, so
Take logarithms; \ln x > 0 since x \ge 2:
For \displaystyle 0 \le t \le \frac12, the series \displaystyle -\ln(1 - t) = t + \frac{t^2}{2} + \frac{t^3}{3} + \cdots gives
With t = 1/p this yields
and \displaystyle \sum_{p \le x} 1/p^2 < \sum_{n \ge 2} \frac{1}{n(n-1)} = 1, a telescoping sum since \displaystyle \frac{1}{n(n-1)} = \frac{1}{n-1} - \frac1n. That is the inequality, and since \ln \ln x \to \infty, the series diverges. \square
Proof of Lemma 3. (a) Since n + k \ge 2k for 1 \le k \le n,
By the binomial theorem the 2n + 1 numbers \binom{2n}{k}, 0 \le k \le 2n, add to 2^{2n} = 4^n. They are positive, so \binom{2n}{n} < 4^n. They increase up to the middle, since \displaystyle \binom{2n}{k+1} / \binom{2n}{k} = \frac{2n - k}{k + 1} \ge 1 for k \le n - 1, and they are symmetric, so \binom{2n}{n} is the largest of them and at least their average 4^n / (2n + 1).
(b) By Theorem 1 applied to (2n)! and to n! twice,
For real y write y = \lfloor y \rfloor + f with 0 \le f < 1; then \lfloor 2y \rfloor - 2\lfloor y \rfloor = \lfloor 2f \rfloor, which is 0 or 1. So each term is 0 or 1, and it is 0 when p^k > 2n. If m is the number of k \ge 1 with p^k \le 2n, then v_p(N) \le m and p^m \le 2n, so p^{v_p(N)} \le 2n.
(c) If n < p \le 2n then p^2 \ge 2p > 2n, so only k = 1 contributes, and \lfloor 2n/p \rfloor - 2\lfloor n/p \rfloor = 1 - 0 = 1. \square
Proof of Theorem 4, the lower bounds. Every prime factor of N = \binom{2n}{n} divides (2n)!, so it is at most 2n. By Lemma 3(b),
so \pi(2n) \ge \ln N / \ln(2n). With N \ge 4^n / (2n + 1) from Lemma 3(a), this is the bound for \pi(2n). For real x \ge 2 let n = \lfloor x/2 \rfloor \ge 1. Then 2n \le x, and with N \ge 2^n,
Finally n \ge x/4: if 2 \le x < 4 then n = 1 > x/4, and if x \ge 4 then n > x/2 - 1 \ge x/4.
The upper bounds. By Lemma 3(c) each prime in (m, 2m] divides \binom{2m}{m}, so their product does (distinct primes, Every number has exactly one prime factorization). With Lemma 3(a), for every integer m \ge 1,
Take m = 2^{j-1} and add over j = 1, \dots, k. Since \theta(1) = 0,
For real x \ge 1 choose k \ge 1 with 2^{k-1} \le x < 2^k. As \theta never decreases, \theta(x) \le \theta(2^k) < 2^{k+1} \ln 2 \le 4x \ln 2 = x \ln 16.
Now let x \ge 2 and split the primes up to x at \displaystyle \sqrt{x}. At most \displaystyle \sqrt{x} of them are at most \displaystyle \sqrt{x}. Each of the other M has \displaystyle \ln p > \frac12 \ln x, so \displaystyle M \cdot \frac12 \ln x \le \theta(x). Hence
Since \ln t \le t - 1 < t for t > 0, taking \displaystyle t = \sqrt{x} gives \displaystyle \ln x < 2\sqrt{x}, that is \displaystyle \sqrt{x} < 2x / \ln x. So \pi(x) < (2 + 8 \ln 2) \, x / \ln x, and 2 + 8 \ln 2 < 7.6. \square
Worked examples
Legendre’s formula on 500!
Find v_2(500!) and v_7(500!), and the largest power of 14 that divides 500!.
SolutionBy Theorem 1, each multiple of 2 up to 500 gives one factor 2, each multiple of 4 one more, and so on, stopping because 2^9 = 512 > 500:
For 7, with 7^4 = 2401 > 500:
Since 14 = 2 \cdot 7, 14^k \mid 500! exactly when k \le 494 and k \le 82, by unique factorization. The largest power is 14^{82}.
The primes inside \binom{30}{15}
Factor \binom{30}{15} = 155{,}117{,}520 with Theorem 1, and check each part of Lemma 3 for n = 15.
SolutionEach prime p \le 30 contributes \lfloor 30/p^k \rfloor - 2\lfloor 15/p^k \rfloor for each k:
- p = 2: (15 - 14) + (7 - 6) + (3 - 2) + (1 - 0) = 4.
- p = 3: (10 - 10) + (3 - 2) + (1 - 0) = 2.
- p = 5: (6 - 6) + (1 - 0) = 1.
- p = 7, 11, 13: 4 - 4, 2 - 2 and 2 - 2, all 0.
- p = 17, 19, 23, 29: 1 - 0 = 1 each.
So
and indeed 720 \cdot 215{,}441 = 155{,}117{,}520. For (b), the prime powers 16, 9, 5, 17, 19, 23, 29 are all at most 30. For (c), the primes in (15, 30] appear exactly once each. For (a), 2^{15} = 32{,}768 and 4^{15}/31 \approx 34{,}636{,}833 are below the coefficient, and 4^{15} = 1{,}073{,}741{,}824 is above it. The terms for 7, 11, 13 cancel (Exercise 14 explains 11 and 13).
The lower-bound argument reads 155{,}117{,}520 \le 30^{\pi(30)}, so \pi(30) \ge \ln(155{,}117{,}520) / \ln 30 \approx 5.5, and \pi(30) \ge 6. The truth is 10.
Euler’s chain at x = 20
Compute the quantities in the proof of Theorem 2 at x = 20.
SolutionThe primes up to 20 are 2, 3, 5, 7, 11, 13, 17, 19, and
Multiplied out, the product holds 1/n for every n \le 20, along with terms such as 1/21 and 1/32 for larger integers built from these primes. So it exceeds \sum_{n \le 20} 1/n \approx 3.60, which exceeds \ln 20 \approx 3.00. On the other side,
The bound is far from sharp here; its force is that the right side grows without limit.
Chebyshev’s bounds at x = 1000
What does Theorem 4 say about \pi(1000)? Compare with \pi(1000) = 168 and with x / \ln x.
SolutionHere \ln 1000 \approx 6.908 and x / \ln x \approx 144.8. The lower bound is \displaystyle \frac{\ln 2}{4} \cdot 144.8 \approx 25.09 and the upper bound 8 \cdot 144.8 \approx 1158.1. Since \pi(1000) is an integer, 26 \le \pi(1000) \le 1158. The bound for \pi(2n) with n = 500 is sharper:
so \pi(1000) \ge 100. The true 168 is about 1.16 times x / \ln x. The bounds are wide; their force is the shape, two fixed multiples of x / \ln x valid for every x.
Density zero, yet a divergent sum
Prove that \pi(x)/x \to 0 as x \to \infty. Then compare the primes with the squares.
SolutionProof. For x \ge 2, Theorem 4 gives 0 \le \pi(x)/x < 8/\ln x, and 8 / \ln x \to 0. By the squeeze theorem, \pi(x)/x \to 0. \square
The squares also have proportion tending to 0: there are \displaystyle \lfloor \sqrt{x} \rfloor of them up to x. Yet \sum 1/n^2 converges (The integral test and p series) while \sum 1/p diverges, so the primes are not as sparse: p_n \ge c\,n^2 for all n, with c > 0, would make \sum 1/p_n converge by comparison. Theorem 4 says more: x / \ln x outgrows x^c for every c < 1 (Comparing growth rates at infinity). The primes are fewer than any fixed proportion of the integers, and more than any power x^c with c < 1.
From the prime number theorem to the nth prime
Assuming Theorem 5, prove that p_n \sim n \ln n. Compare at n = 1000, where p_{1000} = 7919.
SolutionProof. Since \pi(p_n) = n and p_n \to \infty, Theorem 5 at x = p_n gives
Taking logarithms, \ln n + \ln \ln p_n - \ln p_n \to 0. Divide by \ln p_n, which tends to \infty:
The middle term tends to 0, since \ln y / y \to 0 as y \to \infty (here y = \ln p_n). So \ln n / \ln p_n \to 1. Then
\square
At n = 1000, n \ln n \approx 6908 and 7919 / 6908 \approx 1.146.
How many ten-digit primes?
Use Theorem 5 to estimate how many primes have exactly ten digits, and the chance that a random ten-digit integer is prime. The true counts are \pi(10^9) = 50{,}847{,}534 and \pi(10^{10}) = 455{,}052{,}511.
SolutionThe ten-digit integers are those from 10^9 to 10^{10} - 1; neither power of 10 is prime, so the count is \pi(10^{10}) - \pi(10^9). With x / \ln x in place of \pi(x),
The true count is 455{,}052{,}511 - 50{,}847{,}534 = 404{,}204{,}977, about 4.7 percent more. There are 9 \cdot 10^9 ten-digit integers, so the chance is about 0.0449, close to 1 / \ln 10^{10} \approx 1/23.0 from the heuristic.
Theorem 5 alone gives no error at x = 10^{10}; here the true counts confirm the estimate. The same estimate tells RSA key generation to expect about \displaystyle \frac12 \ln x random odd candidates of size x before one is prime.
Boundaries
Asymptotic is not approximate at a given x. Theorem 5 says the ratio tends to 1. It gives no error at any particular x, and the difference \pi(x) - x / \ln x in fact grows without bound (from sharper forms of the theorem, not proved here).
Averages, not gaps. Neighboring primes near x are about \ln x apart on average, but single gaps can be as long as you like (The sieve of Eratosthenes), and whether the gap 2 occurs infinitely often, the twin prime conjecture, is open.
The constants are not sharp. Exercise 16 improves \theta(x) < x \ln 16 to \theta(n) < n \ln 4, and Theorem 5 says the right constant in the limit is 1.
Counting is not locating. Nothing here decides whether a given integer is prime; that is the work of primality tests (RSA and primality tests).
Where this goes next
With 1/p replaced by p^{-s}, Euler’s product becomes the Riemann zeta function: for real s > 1, \sum n^{-s} = \prod (1 - p^{-s})^{-1}, an equality because factorization is unique. The proof of the prime number theorem studies it for complex s, and the Riemann hypothesis about its zeros is equivalent to the sharpest expected error term for \pi(x). Similar methods prove Dirichlet’s theorem, stated in There are infinitely many primes. In this course the density 1 / \ln x sets the cost of finding large primes in RSA and primality tests.
Exercises
Legendre’s formula and binomial coefficients
- Find v_3(200!).
- How many zeros does 300! end with?
- Find the largest k with 12^k \mid 100!.
- Factor \binom{40}{20} into primes with Theorem 1. Which primes up to 20 do not divide it?
- List the primes in (60, 120], and check that their number is less than 120 \ln 2 / \ln 60, as Lemma 3 (a) and (c) imply.
Counting and estimating primes
- Compute \sum_{p \le 50} 1/p and compare it with \ln \ln 50 - 1.
- What lower bounds for \pi(200) do the two lower bounds of Theorem 4 give? Compare with \pi(200) = 46.
- Given \pi(10^4) = 1229 and \pi(10^5) = 9592, compute \pi(x) divided by x / \ln x and by x / (\ln x - 1) at both values.
- Use x / \ln x to estimate \pi(2 \cdot 10^6) - \pi(10^6). The true value is 70{,}435.
- A duathlon numbers its bibs 1 to 5000, and Jasmine and Hiro, at the finish line, hand a medal to every runner whose bib number is prime. Estimate the number of medals with x / \ln x and with x / (\ln x - 1), and compare with \pi(5000) = 669.
- Estimate p_{10{,}000} by n \ln n and by the refinement n(\ln n + \ln \ln n - 1). The true value is 104{,}729.
- How many primes does the heuristic of the Intuition predict between 10^6 and 10^6 + 1000? The true number is 75.
Proofs
- Prove that v_2(n!) = n - s(n) for every positive integer n, where s(n) is the number of 1s in the binary expansion of n.
- Prove that if n \ge 3 and 2n/3 < p \le n for a prime p, then p \nmid \binom{2n}{n}.
- Let m \ge 1. Prove that \binom{2m+1}{m} \le 4^m and that every prime p with m + 1 < p \le 2m + 1 divides \binom{2m+1}{m}.
- Use Exercise 15 and strong induction to prove that the product of the primes up to n is less than 4^n for every integer n \ge 1.
- Using only Theorem 2, prove that for every \varepsilon > 0 there are infinitely many n with p_n < n^{1 + \varepsilon}.
- Assuming Theorem 5, prove that for every \varepsilon > 0 there is an x_0 such that for every x \ge x_0 there is a prime in (x, (1 + \varepsilon)x].
- Prove that if p_n \sim n \ln n, then \pi(x) \sim x / \ln x.
- Prove that x / \ln x \sim x / (\ln x - 1), so Theorem 5 holds with either. Why does Exercise 8 still favor the second?
Answers
- 66 + 22 + 7 + 2 = 97, since 3^5 = 243 > 200.
- Each trailing zero is a factor 10 = 2 \cdot 5. Now v_5(300!) = 60 + 12 + 2, which is 74, and v_2(300!) = 296 is larger, so 300! ends in 74 zeros.
- v_2(100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97 and v_3(100!) = 33 + 11 + 3 + 1 = 48. Since 12 = 2^2 \cdot 3 we need 2k \le 97 and k \le 48, so k = 48.
- The terms \lfloor 40/p^k \rfloor - 2\lfloor 20/p^k \rfloor give v_2 = 1 + 1 = 2 (from 8 and 32), v_3 = 1 + 1 = 2 (from 3 and 27), v_5 = 1 (from 25), v_7 = v_{11} = v_{13} = 1, v_{17} = v_{19} = 0, and 1 for each of 23, 29, 31, 37. So \binom{40}{20} is 2^2 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 times 23 \cdot 29 \cdot 31 \cdot 37, and 17, 19 are missing: \lfloor 40/p \rfloor = 2 = 2\lfloor 20/p \rfloor.
- 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113: thirteen. Their product exceeds 60^{13} and divides \binom{120}{60} < 4^{60}, so 13 \ln 60 < 120 \ln 2, and 120 \ln 2 / \ln 60 \approx 20.3.
- \sum_{p \le 50} 1/p \approx 1.662, against \ln \ln 50 - 1 \approx 0.364.
- With n = 100: (200 \ln 2 - \ln 201)/\ln 200 \approx 25.16, so \pi(200) \ge 26. The bound for all x: \displaystyle \frac{\ln 2}{4} \cdot 200 / \ln 200 \approx 6.54, so \pi(200) \ge 7.
- At 10^4: 1229 / 1085.7 \approx 1.132 and 1229 / 1218.0 \approx 1.009. At 10^5: 9592 / 8685.9 \approx 1.104 and 9592 / 9512.1 \approx 1.008.
- 137{,}849 - 72{,}382 \approx 65{,}466, about 7 percent below 70{,}435.
- 5000 / \ln 5000 \approx 587 and 5000 / (\ln 5000 - 1) \approx 665, against 669 medals.
- n \ln n \approx 92{,}103 and n(\ln n + \ln \ln n - 1) \approx 104{,}307, against 104{,}729.
- One integer in \ln 10^6 \approx 13.8, so about 1000 / 13.8 \approx 72, against 75.
- Write n = \sum_{i \ge 0} b_i 2^i with each b_i \in \{0, 1\}. For k \ge 1, \lfloor n/2^k \rfloor = \sum_{i \ge k} b_i 2^{i-k}, since the dropped part \sum_{i < k} b_i 2^{i-k} lies in [0, 1). By Theorem 1 and swapping the sums, v_2(n!) = \sum_{i} b_i \sum_{k=1}^{i} 2^{i-k}, which is \sum_i b_i (2^i - 1) = n - s(n). \square
- Since p > 2n/3 \ge 2, p \ge 3, so p^2 \ge 3p > 2n and only k = 1 counts. From 2n/3 < p \le n we get 2 \le 2n/p < 3 and 1 \le n/p < 3/2, so \lfloor 2n/p \rfloor - 2\lfloor n/p \rfloor = 2 - 2 = 0. \square
- \binom{2m+1}{m} and \binom{2m+1}{m+1} are equal and are two of the terms adding to 2^{2m+1}, so 2\binom{2m+1}{m} \le 2^{2m+1}. Next, (2m+1)! = \binom{2m+1}{m} \, m! \, (m+1)!, and p divides the left side. Every factor of m!\,(m+1)! is less than p, so by Euclid’s lemma p \nmid m!\,(m+1)!, and Euclid’s lemma again gives p \mid \binom{2m+1}{m}. \square
- Write P(n) for the product. P(1) = 1 < 4 and P(2) = 2 < 16. Let n \ge 3 and assume the claim below n. If n is even, it is not prime, so P(n) = P(n-1) < 4^{n-1} < 4^n. If n = 2m + 1 with m \ge 1, the primes in (m+1, 2m+1] are distinct and divide \binom{2m+1}{m}, so their product is at most 4^m by Exercise 15. Since m + 1 < n, P(n) < 4^{m+1} \cdot 4^m = 4^n. \square So \theta(n) < n \ln 4.
- Suppose not. Then for some \varepsilon > 0 and N, p_n \ge n^{1+\varepsilon} for every n \ge N, so \sum_{n \ge N} 1/p_n \le \sum_{n \ge N} n^{-1-\varepsilon}, which converges as a p-series with exponent 1 + \varepsilon > 1. Then \sum 1/p converges, against Theorem 2. \square
- Let g(x) = x / \ln x and y = (1 + \varepsilon)x. Write \pi(y)/\pi(x) as the product of \pi(y)/g(y), g(y)/g(x) and g(x)/\pi(x). The first and last tend to 1 by Theorem 5, and g(y)/g(x) is (1 + \varepsilon) \ln x over \ln x + \ln(1 + \varepsilon), which tends to 1 + \varepsilon. So \pi(y)/\pi(x) \to 1 + \varepsilon > 1, and \pi(y) > \pi(x) for all x beyond some x_0: a prime lies in (x, y]. \square
- Let g(t) = t / \ln t, increasing for t \ge e. For x \ge 3 let n = \pi(x) \ge 2, so 3 \le p_n \le x < p_{n+1} and g(p_n) \le g(x) < g(p_{n+1}), giving n / g(p_{n+1}) < \pi(x)/g(x) \le n / g(p_n). From p_n \sim n \ln n, \displaystyle \ln p_n = \ln n + \ln \ln n + \ln \frac{p_n}{n \ln n}, so \ln p_n / \ln n \to 1 and g(p_n) \sim n \ln n / \ln n = n; likewise g(p_{n+1}) \sim n + 1 \sim n. As x \to \infty, n = \pi(x) \to \infty, so both outer quotients tend to 1, and so does \pi(x)/g(x). \square
- The ratio of x / \ln x to x / (\ln x - 1) is (\ln x - 1)/\ln x = 1 - 1/\ln x \to 1. Since \sim is transitive, Theorem 5 gives \pi(x) \sim x / (\ln x - 1) too. Asymptotic equality says nothing about the error at a given x, and there the second is much closer. \square