Bertrand's postulate

Bertand's Postulate states that if n is an integer greater than 3, then there is at least one prime between n and 2n-2. It is often stated in the weaker, but perhaps more elegant form: If n is a positive integer, then there is a prime p with n < p ≤ 2n.

In 1845 Bertrand verified this for n less than 3,000,000, and in 1850 Tchebychef gave the first complete proof. In 1932 Erdös gave a much nicer proof using the binomial coefficients, which is the basis of the proof in most modern texts (for example, theorem 418 of [HW79]). This proof can be modified to prove that for any positive integer k, there is a number N such that for all n > N, there are k primes between n and 2n.

Notice Bertrand's postulate tells us that for any prime p, there is another prime less than 2p, so we have the weak result that the nth prime p_n is at most 2ⁿ. This gives us the following way to create a formula for the nth prime: Let r be any integer greater than one, then let a be the sum

p₁r^-1 + p₂r^-4 + p₃r^-9 + ... + p_nr ^{- n2} + ...

The nth prime is given by

p_n = floor(rⁿ²a) - r^2n-1floor(r ^(n-1)2a)

This is cute, but computationally useless.

See Also: PrimeNumberThm, FormulasForPrimes

References:

HW79 (chapter 22)

G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Oxford University Press, 1979.  ISBN 0198531702. MR 81i:10002 (Annotation available)