Archive for 11th October 2008

Heuristic Derivation of Prime Number Theorem

The Prime Number theorem says that the probability P(x) that a large integer x is prime is about 1/log x. At about age 16 Gauss apparently conjectured this estimate after studying tables of primes. Hugh Bray via Greg Martin suggested to me the following heuristic way to approach the same conjecture, which appeared in my Math Chat column on August 19, 1999:

Suppose that there is a nice probability function P(x) that a large integer x is prime. As x increases by \Delta x = 1, the new potential divisor x is prime with probability P(x) and divides future numbers with probability 1/x. Hence P gets multiplied by (1-P/x),\Delta P = -P^2/x, or roughly

P' = -P^2/x.

The general solution to this differential equation is P(x) = 1/log cx.