- #1

- 2,123

- 79

## Main Question or Discussion Point

The largest known primes for some time have all been Mersenne primes. Can it be shown either that there may exist or cannot exist unknown primes less than the largest known prime?

- Thread starter SW VandeCarr
- Start date

- #1

- 2,123

- 79

The largest known primes for some time have all been Mersenne primes. Can it be shown either that there may exist or cannot exist unknown primes less than the largest known prime?

- #2

mgb_phys

Science Advisor

Homework Helper

- 7,774

- 12

I'm not sure you can even prove that there aren't other Mersenne primes between the those found.

Last edited:

- #3

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

There are more than 10The largest known primes for some time have all been Mersenne primes. Can it be shown either that there may exist or cannot exist unknown primes less than the largest known prime?

So yes, there are unknown primes beneath the largest known prime.

* In particukar, there are between 1.05901756822452 × 10

- #4

mgb_phys

Science Advisor

Homework Helper

- 7,774

- 12

That you can even calculate such a number is truly amazing!There are more than 10^{12978181}primes

- #5

- 2,123

- 79

Thanks GR Greathouse.If you're talking only about other Mersenne primes, mgb_phys answered it: we have no idea. But to answer your literal question:

There are more than 10^{12978181}primes* beneath the largest known Mersenne prime. If storing each prime takes 1 bit, there has not been enough storage media produced on Earth through all history (hard drives, DVDs, clay tablets) to hold all these primes.

So yes, there are unknown primes beneath the largest known prime.

* In particukar, there are between 1.05901756822452 × 10^{12978181}and 1.05901756822453 × 10^{12978181}primes in that range, thanks to Pierre Dusart's tight bounds on pi(x).

If I wanted to enumerate the primes over some tractable interval less than the largest known prime , would it be any easier given that at least one prime greater than the upper bound of the interval is known?

- #6

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

No, it would be just as hard. There's no good way to use that information.If I wanted to enumerate the primes over some tractable interval less than the largest known prime , would it be any easier given that at least one prime greater than the upper bound of the interval is known?

- #7

- 2,123

- 79

I appreciate your patience with me. Just one more (two part) related question:No, it would be just as hard. There's no good way to use that information.

If I wanted to construct an unbroken sequence of all primes up to some prime p', would this limit be determined only by the limits of computability (brute force and/or algorithmic)? Is there any information regarding about what this limit might be?

Thanks in advance.

Last edited:

- #8

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

I don't mind answering your questions.I appreciate your patience with me. Just one more (two part) related question:

I don't understand what you're asking. But practically, if you want to make a huge list of primes, the issue you'll run into is storage: the memory needed for an efficient search (say, at least 20 * sqrt(n)/log(n) bytes to search up to n), and the hard drive (or whatever) space to keep the primes you find (say, 16 * n / log(n) bytes to store the primes up to n, or an eighth that amount for just the differences). So if you wanted a list of primes up to 10^20, you'd need several million terabytes of hard drive space (tens of millions unless you just store the differences).If I wanted to construct an unbroken sequence of all primes up to some prime p', would this limit be determined only by the limits of computability (brute force and/or algorithmic)? Is there any information regarding about what this limit might be?

- #9

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

They are.1)I'm trying to confirm that all primes up the largest known prime (or any arbitrarily large prime (p')) are in principle computable (Turing definition).

There are algorithms that, given enough memory, can compute primes up to n faster than iterating through 1, 2, ..., n. So storage becomes the limiting concern there. You could fill a 250 GB hard drive with primes, but what then? It's often faster to generate them and use them on the fly anyway -- don't bother with the (slow) hard drive.2) Practically there is always a lot of interest in new largest prime, but none (as far as I can tell) as to the longest unbroken sequence of primes from 2 to p' . It seems such lists this would have utility for codes, "random" sequences and simply examining the statistical properties of such sequences. For example, do we know the first 10^6 or 10^7 primes?

- #10

- 2,123

- 79

Thanks for your answers CRGreathouse. That's what I'll do.They are.

There are algorithms that, given enough memory, can compute primes up to n faster than iterating through 1, 2, ..., n. So storage becomes the limiting concern there. You could fill a 250 GB hard drive with primes, but what then? It's often faster to generate them and use them on the fly anyway -- don't bother with the (slow) hard drive.

- #11

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

May I ask what your application is?Thanks for your answers CRGreathouse. That's what I'll do.

- #12

- 2,123

- 79

I'm interested in the statistical distribution of primes as it relates to some interesting research in self-organizing processes. There's a number of papers on the net regarding this. I'm a retired epidemiologist.May I ask what your application is?

- #13

- 841

- 0

Just out of curiosity and possibly to help the originator of this thread, can someone point to a source for such a list generating algorithm. I know of prime lists of the first n primes, n = 10,000 or lower are the typical lists of primes that I have seen, but as to the quickest or most powerful list generator, I have no idea of where to look.They are.

There are algorithms that, given enough memory, can compute primes up to n faster than iterating through 1, 2, ..., n. So storage becomes the limiting concern there. You could fill a 250 GB hard drive with primes, but what then? It's often faster to generate them and use them on the fly anyway -- don't bother with the (slow) hard drive.

Last edited:

- #14

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

The Sieve of Atkin is the asymptotically fastest method I know. Bernstein has an excellent implementation on his site.Just out of curiosity and possibly to help the originator of this thread, can someone point to a source for such a list generating algorithm. I know of prime lists of the first n primes, n = 10,000 or lower are the typical lists of primes that I have seen, but as to the quickest or most powerful list generator, I have no idea of where to look.

- #15

- 1,838

- 7

- #16

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

Not if you want an exact answer.

- Last Post

- Replies
- 6

- Views
- 2K

- Replies
- 1

- Views
- 2K

- Replies
- 2

- Views
- 6K

- Replies
- 6

- Views
- 3K

- Replies
- 6

- Views
- 3K

- Last Post

- Replies
- 6

- Views
- 6K

- Replies
- 14

- Views
- 5K

- Replies
- 2

- Views
- 3K