Large Prime Numbers

Date: 01/13/2009 at 13:10:02
From: Dave
Subject: Large primes

What is the largest prime number less than which all primes are 
known? (We might call this the largest "contiguous" prime.)

I haven't been able to find this out on the web.  There is a lot of 
discussion about the largest primes known, of course, but not 
on "contiguous" primes.  Presumably this list is always changing, but 
I'm trying to find out how high that list goes right now.

Date: 01/13/2009 at 15:43:50
From: Doctor Vogler
Subject: Re: Large primes

Hi Dave,

Thanks for writing to Dr. Math.  Answering that question is more a
matter of figuring out what you consider "known" than solving a math
problem.  Using the Sieve of Eratosthenes (or a modern variation known
as the Sieve of Atkins), computers can generate consecutive prime
numbers faster than they can store them to disk.  You can download
lists of primes, but when you want a really long list, it's faster to
download a program that will generate the list for you.

If by "known" you mean that some human knows that this particular
number is prime, then I'm sure the largest contiguous prime is quite
small.  If by "known" you mean that there is a list of primes stored
on some computer disk up to this number, then it's probably somewhere
in the trillions.  But that number would be subject to change, because
the person who used several terabytes of disk storage to save the list
probably didn't do so just to make a record; he was probably using
them.  And when he is done with them, then he is likely to delete the
list and use those terabytes of storage for something else.

You can get a lower bound for this number by downloading a prime
number generator and filling up your own hard disk with primes.

If by "known" you mean that some computer program at some point
generated all primes up to this number but, due to a lack of space to
store them all, didn't record the full list, then it might be in the
hundreds or thousands of trillions, but it would be hard to find this
out and harder still to substantiate/verify someone's claim of having
computed all primes up to some huge number.  And why would you bother
to compute them if you weren't going to store them?  Only if you had
need of a longer list of consecutive primes than you were willing or
able to store to disk.

Certainly, the number is smaller than the trillions-of-trillions 
range, since even the more efficient Sieve of Atkins takes O(n)
operations to find the primes up to n, and a trillion trillion is
10^24 (or about 2^80).  Well, a modern computer might run around 4
GHz, or 4 * 10^9 operations per second, or about 1.26 * 10^17
operations per year.  So it would take a million computers running at
4 GHz for almost 10 years to do 10^24 operations, and I don't think
anyone is going to use that kind of resource for that long generating
prime numbers.

On the other hand, testing a single number around 2^80 (or even much
larger than that) is very fast and can be done in a fraction of a
second on a computer.  But numbers with many more digits take a lot
longer to verify that they are prime.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 01/13/2009 at 18:26:36
From: Dave
Subject: Thank you (Large primes)

Thank you!  This was very helpful.