math.wiki
Number theory › Divisibility and primes › How the primes are spread out
Sign in

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
Number theory3
Divisibility and primes1
How the primes are spread out

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

\theta(x) = \sum_{p \le x} \ln p

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

50 100 150 200 0 10 20 30 40
\pi(x)
\dfrac{x}{\ln x}
x
Figure 1The prime counting function \pi(x) against x / \ln x for x \le 200.

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.

10 100 1000
10^{4}
10^{5}
10^{6}
0.9 1.0 1.1 1.2 1.3
\pi(x) \ln x \,/\, x
x (logarithmic scale)
Figure 2The ratio \pi(x) \ln x / x, with x on a logarithmic scale. It tends to 1, but slowly.

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,

v_p(n!) = \sum_{k \ge 1} \left\lfloor \frac{n}{p^k} \right\rfloor

The sum is finite: its terms are 0 once p^k > n.

Theorem 2 (Euler). For every real x \ge 2,

\sum_{p \le x} \frac{1}{p} > \ln \ln x - 1

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,

\frac{\ln 2}{4} \cdot \frac{x}{\ln x} \le \pi(x) < 8 \cdot \frac{x}{\ln x}

Moreover \theta(x) < x \ln 16 for every real x \ge 1, and for every integer n \ge 1,

\pi(2n) \ge \frac{2n \ln 2 - \ln(2n + 1)}{\ln(2n)}

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).

\pi(x) \sim \frac{x}{\ln x}

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,

v_p(n!) = \sum_{j=1}^{n} v_p(j)

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

1 + \frac1p + \cdots + \frac{1}{p^K} < \frac{1}{1 - 1/p}

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

\prod_{p \le x} \frac{1}{1 - 1/p} > \sum_{n \le x} \frac1n

With N = \lfloor x \rfloor, 1/n \ge 1/t for n \le t \le n + 1, so

\sum_{n \le x} \frac1n \ge \int_1^{N+1} \frac{dt}{t} = \ln(N + 1) > \ln x

Take logarithms; \ln x > 0 since x \ge 2:

\sum_{p \le x} -\ln\left(1 - \frac1p\right) > \ln \ln x

For \displaystyle 0 \le t \le \frac12, the series \displaystyle -\ln(1 - t) = t + \frac{t^2}{2} + \frac{t^3}{3} + \cdots gives

\begin{aligned} -\ln(1 - t) &\le t + \frac{t^2}{2}\left(1 + t + t^2 + \cdots\right) \\ &= t + \frac{t^2}{2(1 - t)} \le t + t^2 \end{aligned}

With t = 1/p this yields

\sum_{p \le x} \frac1p + \sum_{p \le x} \frac{1}{p^2} > \ln \ln x

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,

\begin{aligned} \binom{2n}{n} &= \frac{(2n)!}{n! \, n!} \\ &= \prod_{k=1}^{n} \frac{n + k}{k} \ge 2^n \end{aligned}

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,

\begin{aligned} v_p(N) &= \sum_{k \ge 1} t_k, \\ t_k &= \left\lfloor \frac{2n}{p^k} \right\rfloor - 2\left\lfloor \frac{n}{p^k} \right\rfloor \end{aligned}

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),

N = \prod_{p \le 2n} p^{v_p(N)} \le (2n)^{\pi(2n)}

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,

\pi(x) \ge \pi(2n) \ge \frac{n \ln 2}{\ln(2n)} \ge \frac{n \ln 2}{\ln x}

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,

\begin{aligned} \theta(2m) - \theta(m) &= \ln \prod_{m < p \le 2m} p \\ &\le \ln \binom{2m}{m} < 2m \ln 2 \end{aligned}

Take m = 2^{j-1} and add over j = 1, \dots, k. Since \theta(1) = 0,

\theta(2^k) < (2 + 4 + \cdots + 2^k) \ln 2 < 2^{k+1} \ln 2

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

\begin{aligned} \pi(x) &\le \sqrt{x} + \frac{2\theta(x)}{\ln x} \\ &< \sqrt{x} + \frac{8 \ln 2 \cdot x}{\ln x} \end{aligned}

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

Example 1

Legendre’s formula on 500!

Find v_2(500!) and v_7(500!), and the largest power of 14 that divides 500!.

Solution

By 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:

\begin{aligned} v_2(500!) &= 250 + 125 + 62 + 31 \\ &\quad + 15 + 7 + 3 + 1 = 494 \end{aligned}

For 7, with 7^4 = 2401 > 500:

v_7(500!) = 71 + 10 + 1 = 82

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}.

Example 2

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.

Solution

Each 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

\binom{30}{15} = 2^4 \cdot 3^2 \cdot 5 \cdot 17 \cdot 19 \cdot 23 \cdot 29

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.

Example 3

Euler’s chain at x = 20

Compute the quantities in the proof of Theorem 2 at x = 20.

Solution

The primes up to 20 are 2, 3, 5, 7, 11, 13, 17, 19, and

\prod_{p \le 20} \frac{p}{p - 1} = \frac{323{,}323}{55{,}296} \approx 5.85

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,

\sum_{p \le 20} \frac1p \approx 1.455 > \ln \ln 20 - 1 \approx 0.097

The bound is far from sharp here; its force is that the right side grows without limit.

Example 4

Chebyshev’s bounds at x = 1000

What does Theorem 4 say about \pi(1000)? Compare with \pi(1000) = 168 and with x / \ln x.

Solution

Here \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:

\pi(1000) \ge \frac{1000 \ln 2 - \ln 1001}{\ln 1000} \approx 99.3

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.

Example 5

Density zero, yet a divergent sum

Prove that \pi(x)/x \to 0 as x \to \infty. Then compare the primes with the squares.

Solution

Proof. 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.

Example 6

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.

Solution

Proof. Since \pi(p_n) = n and p_n \to \infty, Theorem 5 at x = p_n gives

\frac{n \ln p_n}{p_n} \to 1

Taking logarithms, \ln n + \ln \ln p_n - \ln p_n \to 0. Divide by \ln p_n, which tends to \infty:

\frac{\ln n}{\ln p_n} + \frac{\ln \ln p_n}{\ln p_n} - 1 \to 0

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

\begin{aligned} \frac{p_n}{n \ln n} &= \frac{p_n}{n \ln p_n} \cdot \frac{\ln p_n}{\ln n} \\ &\to 1 \cdot 1 = 1 \end{aligned}

\square

At n = 1000, n \ln n \approx 6908 and 7919 / 6908 \approx 1.146.

Example 7

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.

Solution

The 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),

\begin{aligned} &\frac{10^{10}}{\ln 10^{10}} - \frac{10^9}{\ln 10^9} \\ &\approx 386{,}039{,}540 \end{aligned}

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

  1. Find v_3(200!).
  2. How many zeros does 300! end with?
  3. Find the largest k with 12^k \mid 100!.
  4. Factor \binom{40}{20} into primes with Theorem 1. Which primes up to 20 do not divide it?
  5. 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

  1. Compute \sum_{p \le 50} 1/p and compare it with \ln \ln 50 - 1.
  2. What lower bounds for \pi(200) do the two lower bounds of Theorem 4 give? Compare with \pi(200) = 46.
  3. 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.
  4. Use x / \ln x to estimate \pi(2 \cdot 10^6) - \pi(10^6). The true value is 70{,}435.
  5. 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.
  6. 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.
  7. How many primes does the heuristic of the Intuition predict between 10^6 and 10^6 + 1000? The true number is 75.

Proofs

  1. 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.
  2. Prove that if n \ge 3 and 2n/3 < p \le n for a prime p, then p \nmid \binom{2n}{n}.
  3. 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}.
  4. 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.
  5. Using only Theorem 2, prove that for every \varepsilon > 0 there are infinitely many n with p_n < n^{1 + \varepsilon}.
  6. 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].
  7. Prove that if p_n \sim n \ln n, then \pi(x) \sim x / \ln x.
  8. 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
  1. 66 + 22 + 7 + 2 = 97, since 3^5 = 243 > 200.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. \sum_{p \le 50} 1/p \approx 1.662, against \ln \ln 50 - 1 \approx 0.364.
  7. 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.
  8. 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.
  9. 137{,}849 - 72{,}382 \approx 65{,}466, about 7 percent below 70{,}435.
  10. 5000 / \ln 5000 \approx 587 and 5000 / (\ln 5000 - 1) \approx 665, against 669 medals.
  11. n \ln n \approx 92{,}103 and n(\ln n + \ln \ln n - 1) \approx 104{,}307, against 104{,}729.
  12. One integer in \ln 10^6 \approx 13.8, so about 1000 / 13.8 \approx 72, against 75.
  13. 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
  14. 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
  15. \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
  16. 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.
  17. 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
  18. 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
  19. 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
  20. 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
math.wiki · updated 2026-11-18 · CC-BY-SA-4.0