Re: Space between prime numbers

From: Keith A. Lewis (klewis_at_LUMINA.MITRE.ORG)
Date: 03/28/05 

Date: Mon, 28 Mar 2005 15:38:43 +0000 (UTC)

Richard Cavell <richardcavell@mail.com> writes in article <d292bk$***$1@nnrp.waia.asn.au> dated Tue, 29 Mar 2005 00:04:26 +1000:
>Given any prime number, I wonder if there is a way to predict what the
>gap will be between it and the next prime number.

The density of primes around x is approximately 1/ln(x), so the expected
value of the gap is approximately ln(x). But obviously it varies from the
expected value.

>Obviously you can make good guesses (only examine odd numbers, etc) and
>then you can test for primality.
>
>It is said that prime numbers are irregularly spaced. How does one
>prove this? Obviously the sieve of Eratosthenes implies there is indeed
>a pattern to the prime numbers, even if it's not immediately obvious.

That sieve grows more complex with each added prime. But even a partial
implementation (say, 2-17 which gives you a mod 510510 filter) will give
you a nice solid lower bound for the gap you're interested in.

--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.

Quantcast