Cramér’s Conjecture

Cramér’s conjecture proposes that the gap between consecutive prime numbers $ p_n $ and $ p_{n+1} $ satisfies the following asymptotic bound: $$ p_{n+1} - p_n = O((\log p_n)^2) $$

In other words, the difference between two consecutive primes is at most proportional to the square of the natural logarithm of the first prime $ p_n $, setting an upper limit on the interval in which the next prime appears.

This means that while prime gaps $ p_{n+1} - p_n $ can grow arbitrarily large, they do not exceed $ (\log p_n)^2 $ in terms of order of magnitude.

Note. This conjecture was introduced by Harald Cramér in 1936 as part of his work on prime number distribution. It provides insight into how primes are spaced and is closely tied to the study of prime gaps. While numerical evidence supports the conjecture, it remains unproven. If true, it would offer a precise characterization of prime number distribution and mark a major breakthrough in analytic number theory.

Cramér’s conjecture states that the gap between consecutive primes $ p_{n+1} - p_n $ is bounded by $ O((\log p_n)^2) $, but it does not indicate the exact position of the next prime.

In other words, the conjecture provides an upper asymptotic bound but does not offer a way to precisely determine the location of the next prime.

Practical Example
Additional Notes

Practical Example

Consider the third prime number: $ p_3 = 5 $

$$ p_3 = 5 $$

We compute the square of the natural logarithm of 5: $ (\log 5)^2 \approx 2.59 $.

$$ p_{n+1} - p_n = O((\log p_n)^2) $$

$$ p_{4} - 5 = O((\log 5)^2) $$

$$ p_{4} - 5 = O(2.59) $$

This means the next prime must be within the interval $ (5, 5 + 2.59) $, or $ (5, 7.59) $.

Indeed, the next prime is $ p_4 = 7 $, with $ p_4 - p_3 = 2 $, which is well within the predicted bound $ (\log 5)^2 = 2.59 $.

Example 2

Now consider the prime:

$$ p_n = 101 $$

We compute the square of the natural logarithm of 101: $ (\log 101)^2 \approx 21.31 $.

$$ p_{n+1} - p_n = O((\log p_n)^2) $$

$$ p_{n+1} - 101 = O((\log 101)^2) $$

$$ p_{n+1} - 101 = O(21.31) $$

This means the next prime falls within the range $ (101, 101 + 21.31) $, or $ (101, 122.31) $.

In this case, the next prime is $ p_{n+1} = 103 $, with $ p_{n+1} - p_n = 2 $, which is significantly smaller than $ (\log 101)^2 = 21.31 $.

Note. The interval $ (101, 122.31) $ contains several prime numbers: $ 103, 107, 109, 113 $. The smallest of these is $ p_{n+1} = 103 $. Cramér’s conjecture holds because the prime gap $ 103 - 101 = 2 $ is much smaller than the theoretical bound $ (\log 101)^2 = 21.31 $.

Additional Notes

Some observations and remarks.

Cramér’s conjecture is not the best way to find the next prime
While Cramér’s conjecture provides an upper bound for prime gaps, it is not an efficient method for determining the next prime. It still requires a primality test to filter out composite numbers within the predicted range. Moreover, since the conjecture remains unproven, it is possible that extreme cases (for extremely large numbers) could violate this bound. As a result, Cramér’s conjecture is useful for estimating where the next prime might lie and for theoretical analysis, but for practical prime-finding, direct primality tests are more reliable.
Note. To determine the next prime after $ p_n $ (where $ p_n > 2 $), a more effective approach is to apply a primality test directly to successive odd numbers $ p_n + 2 $ using an efficient algorithm such as trial division up to $ \sqrt{n} $ or more advanced methods like Miller-Rabin. For example, according to Cramér’s conjecture, the next prime after $ 101 $ should be somewhere in the interval $ (101, 122.31) $. However, testing the primality of successive odd numbers reveals that the next prime is $ p_{n+1} = 103 $, without needing to compute the theoretical bound.

And so on.