Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 37 ยท Divisibility and Primes

How Primes Are Distributed

Explore how primes thin out: infinitely many primes, the prime counting function, the Prime Number Theorem, prime gaps, twin primes and Dirichlet's theorem, with Python plots.

There are infinitely many primes, but they get rarer as you go up. Of the numbers below 10 there are 4 primes; below 100 there are 25; below 1,000 there are 168; below a million there are 78,498. How fast do they thin out? Are they spread evenly, or do they clump? This lesson looks at what mathematicians know and how you can see it for yourself.

You will use the prime counting function ฯ€(x), meet the Prime Number Theorem (which describes the average density), look at gaps between primes, and finish with primes in arithmetic progressions.

The prime counting function

ฯ€(x) is the number of primes that are at most x. So ฯ€(10) = 4 (2, 3, 5, 7) and ฯ€(100) = 25. Compute it with a sieve.

Python Counting primes and comparing with x / ln x

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Prime Number Theorem

Around 1800 Gauss and Legendre guessed from tables like this one that ฯ€(x) is approximately x / ln x. In 1896 Hadamard and de la Vallรฉe Poussin proved it independently:

ฯ€(x) ~ x / ln x, meaning the ratio tends to 1 as x grows.

Equivalent and more intuitive: the chance that a random number near x is prime is about 1 / ln x. Near 100 about one number in 4.6 is prime, near a million about one in 14, and near 10ยนโฐโฐ about one in 230. A closer approximation is the logarithmic integral Li(x) = โˆซ dt / ln t, which is much more accurate.

Python Plot pi(x) against two approximations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The curve for x / ln x sits visibly below ฯ€(x) while the Li(x) dots follow ฯ€(x) closely.

Gaps between primes

The gap after a prime p is the distance to the next prime. The first gaps are 1, 2, 2, 4, 2, 4 (2โ†’3, 3โ†’5, 5โ†’7, 7โ†’11, 11โ†’13, 13โ†’17). Two surprising facts hold together:

  • Gaps can be as large as you like. For any n, the n consecutive numbers (n+1)! + 2, (n+1)! + 3, ..., (n+1)! + (n+1) are all composite, because each is divisible by its second term.
  • Yet small gaps keep occurring. Pairs of primes that differ by 2 (twin primes) such as (11, 13) and (17, 19) seem to appear forever, but this remains unproven. In 2013 Zhang proved gaps below 70 million occur infinitely often; later work lowered the bound to 246.
Python Gaps, records and long composite runs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Primes in arithmetic progressions

Do primes avoid certain remainders? Take the progression 4k + 1 and 4k + 3: both contain infinitely many primes, and the counts below a limit are close to equal. But 4k + 2 contains only the prime 2, because every such number is even. In general a progression a, a + m, a + 2m, ... can only contain many primes if gcd(a, m) = 1. Dirichlet's theorem (1837) says that is also sufficient: if gcd(a, m) = 1 there are infinitely many primes of the form a + km. The primes are shared evenly between the ฯ†(m) allowed residue classes in the long run.

Python Primes by last digit and by remainder mod 4

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You will see that primes (except 2 and 5) end only in 1, 3, 7 or 9, with nearly equal counts, and that classes 1 and 3 mod 4 are almost balanced.

flowchart LR
  A["Infinitely many primes (Euclid)"] --> B["Density 1/ln x (PNT)"]
  B --> C["Gaps: arbitrarily large, often small"]
  B --> D["Equal shares in each coprime residue class (Dirichlet)"]

Four views of how primes are spread out.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the Prime Number Theorem say?

    The ratio of pi(x) to x/ln x tends to 1.
  2. 2. Roughly what fraction of numbers near 1,000,000 are prime?

    1 / ln(10^6) is about 1/13.8, so about one in 14.
  3. 3. How can you build a run of 10 consecutive composite numbers?

    Each 11! + k with 2 <= k <= 11 is divisible by k.
  4. 4. Which progression contains infinitely many primes by Dirichlet's theorem?

    gcd(7, 10) = 1. The other progressions share a factor with their modulus, so they contain at most one prime.

Summary

  • ฯ€(x) counts primes up to x; ฯ€(100) = 25 and ฯ€(10โถ) = 78,498.
  • The Prime Number Theorem: ฯ€(x) ~ x / ln x, so a random number near x is prime with probability about 1/ln x.
  • Prime gaps can be arbitrarily large (factorial runs) yet small gaps occur again and again.
  • Twin primes are conjectured infinite but unproven.
  • Dirichlet: a progression a + km has infinitely many primes exactly when gcd(a, m) = 1.

Next: Congruences: The Basics