This site is supported by donations to The OEIS Foundation.

Prime number theorem

The prime number theorem concerns the distribution of prime numbers. Young Carl Friedrich Gauß suspected a simple division of a number by its logarithm would give a pretty good idea of how many primes there are up to that number.[1] But throughout the 19th century mathematicians, including Gauß himself, came up with much more complicated formulas, until Jacques Hadamard and Charles Jean Gustave Nicolas de la Vallée-Poussin proved the prime number theorem independently of each other in 1896. Paul Erdős came up with an elementary proof in 1949, but it is elementary only in the sense that it does not use complex analysis like the Hadamard or de la Vallée-Poussin proofs.

Theorem. Given the prime counting function π(x), the following limit holds:

$\lim_{x \to \infty} \frac{\pi(x) \log x}{x} = 1 \,$[2]

For small numbers, this seems to be wrong (for example, compare A050499 to A000720). But for large numbers, this is surprisingly close to correct, and, as the frivolous theorem of arithmetic tells us, almost all numbers are very large.

Even an elementary proof is much too long to be given here.

1. Dan Rockmore, Stalking the Riemann Hypothesis: The Quest to Find the Hidden Law of Prime Numbers. New York: Pantheon Books (2005) p. 41
2. Manfred R. Schroeder, Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing and Self-Similarity, 5th Ed. Springer (2009) p. 50.