# Largest Prime Number in the sequence **URL:** \ **Category:** Factual Questions\ **Created:** [June 29, 2002, 2:16am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503 "2002-06-29T02:16:11Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![andy\_fl](https://avatars.discourse-cdn.com/v4/letter/a/49beb7/32.png) [@andy\_fl](https://boards.straightdope.com/u/andy_fl)\ **Post date:** [June 29, 2002, 2:16am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/1 "2002-06-29T02:16:11Z")
I have seen many big prime numbers. But my question is - Whats the largest known prime number, such that **all** lesser prime numbers are also known ? Also, how **many** prime numbers are there between this prime number and the first prime number ? ---
**Author:** ![jbird3000](https://avatars.discourse-cdn.com/v4/letter/j/aeb1de/32.png) [@jbird3000](https://boards.straightdope.com/u/jbird3000)\ **Post date:** [June 29, 2002, 2:38am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/2 "2002-06-29T02:38:09Z")
Searched for “largest prime number” on Google. First entry is this [http://www.utm.edu/research/primes/largest.html](http://www.utm.edu/research/primes/largest.html) . It says 2^13466917-1. I’d assume that all the prime numbers lower than that have also been found. As for the second question, I don’t feel like looking it up. ---
**Author:** ![Arnold\_Winkelried](https://avatars.discourse-cdn.com/v4/letter/a/3d9bf3/32.png) [@Arnold\_Winkelried](https://boards.straightdope.com/u/Arnold_Winkelried)\ **Post date:** [June 29, 2002, 2:48am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/3 "2002-06-29T02:48:03Z")
I’ll bet you $5.00 that 2^13466917 + 13 is also prime. ---
**Author:** ![Taran](https://avatars.discourse-cdn.com/v4/letter/t/edb3f5/32.png) [@Taran](https://boards.straightdope.com/u/Taran)\ **Post date:** [June 29, 2002, 2:50am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/4 "2002-06-29T02:50:38Z")
Sadly, we don’t know all prime numbers less than (2^13466917)-1. As [this page](http://www.utm.edu/research/primes/notes/13466917) outlines, the guy who found this one typed (2^13466917)-1 into a prime number finder and let it run in the background for 43 days. So, we’re missing a large number of primes between 2 and (2^13466917)-1. As to the OP, I have no idea whatsoever. ---
**Author:** ![Arnold\_Winkelried](https://avatars.discourse-cdn.com/v4/letter/a/3d9bf3/32.png) [@Arnold\_Winkelried](https://boards.straightdope.com/u/Arnold_Winkelried)\ **Post date:** [June 29, 2002, 2:54am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/5 "2002-06-29T02:54:11Z")
Damn you, submit button! The number of primes \<= x can be approximated using the [prime number theorem](http://www.wikipedia.com/wiki/prime+number+theorem): pi(x) ~ x / ln (x) ---
**Author:** ![The\_Peyote\_Coyote](https://avatars.discourse-cdn.com/v4/letter/t/5f8ce5/32.png) [@The\_Peyote\_Coyote](https://boards.straightdope.com/u/The_Peyote_Coyote)\ **Post date:** [June 29, 2002, 3:12am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/6 "2002-06-29T03:12:06Z")
andy\_fl: Do not think we will ever know what the largest prime number is. The set of primes is infinite ---
**Author:** ![MarkyDeSade](https://avatars.discourse-cdn.com/v4/letter/m/35a633/32.png) [@MarkyDeSade](https://boards.straightdope.com/u/MarkyDeSade)\ **Post date:** [June 29, 2002, 3:31am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/7 "2002-06-29T03:31:46Z")
> [@](#): > > Do not think we will ever know what the largest prime number is. The set of primes is infinite Prove it. 😉 ---
**Author:** ![Bryan\_Ekers](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bryan_ekers/32/183_2.png) [@Bryan\_Ekers](https://boards.straightdope.com/u/Bryan_Ekers)\ **Post date:** [June 29, 2002, 4:00am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/8 "2002-06-29T04:00:32Z")
Proving it is easy. Assume the set of Primes is finite, consisting of {P1, P2, P3, … P_n_} Now imagine a number, M, which is equal to P1 x P2 x P3 x … P_n_, i.e. M is the product of all known prime numbers, and is therefore divisible by each of them. M+1 isn’t divisible by _any_ of them. Therefore M+1 is a prime and larger than P_n_. And if you add M+1 to your set of primes, you can generate and een larger prime, _ad infinitum_. The process that generates primes that look like powers of 2, with 1 subtracted, is well established but does not generate every possible prime. The exponent itself must be prime. Generic 2[sup]_n_[/sup] - 1 values are called Mersenne Numbers, and if the result is a prime, the term Mersenne Prime is used. 2[sup]2[/sup] - 1 = 3 (prime) 2[sup]3[/sup] - 1 = 7 (prime, but it skipped over 5) 2[sup]5[/sup] - 1 = 31 (prime, but it skipped over numerous primes) Skipping ahead: 2[sup]11[/sup] - 1 = 2047 which is not prime, being equal to 89x23. Generating Mersenne Numbers is easy, but proving they’re Mersenne Primes really chews up the clock cycles. ---
**Author:** ![Bryan\_Ekers](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bryan_ekers/32/183_2.png) [@Bryan\_Ekers](https://boards.straightdope.com/u/Bryan_Ekers)\ **Post date:** [June 29, 2002, 4:01am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/9 "2002-06-29T04:01:57Z")
“you can generate _an even_ larger prime”, rather. ---
**Author:** ![perspective](https://avatars.discourse-cdn.com/v4/letter/p/f475e1/32.png) [@perspective](https://boards.straightdope.com/u/perspective)\ **Post date:** [June 29, 2002, 5:07am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/10 "2002-06-29T05:07:32Z")
As long as we’re talking about Mersennes: how about the Catalan sequence? 2[sup]2[/sup] - 1 = 3 (prime) 2[sup]3[/sup] - 1 = 7 (prime) 2[sup]7[/sup] - 1 = 127 (prime) 2[sup]127[/sup] - 1 =170141183460469231731687303715884105727( prime) 2[sup]170141183460469231731687303715884105727[/sup] - 1 =??? unknown The OP is the sort of thing that could change from day to day. But to give an idea, I found a sieve that “finds” all of the primes below 2,000,000,009. [http://www.rsok.com/~jrm/printprimes.html](http://www.rsok.com/~jrm/printprimes.html) Lots of other cool links for prime questions there. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [June 29, 2002, 7:21am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/11 "2002-06-29T07:21:08Z")
Correct me if I’m wrong, but the proof that **Bryan Ekers** uses is one of the classic proofs of Arithmetic, and goes all the way back to Euclid. One reason that the highest prime we know is so much astronomically higher than the prime asked for in the OP is this: little achievement for a lot of work. I imagine that in the Number Theory community, you’d get a certain amount of recognition for finding the highest prime, and a comparable amount for finding the prime that the OP asks for. However, in order to find the highest prime, you only have to deal with one number. That’s it. One. In order to find the highest prime number with no gaps below it, you would have to prove that a whole heck of a lot of numbers are composite. Proving that a certain 16-digit number is composite doesn’t get you a lot of recognition, I imagine. There are a lot of 16-digit composites. ---
**Author:** ![Bryan\_Ekers](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bryan_ekers/32/183_2.png) [@Bryan\_Ekers](https://boards.straightdope.com/u/Bryan_Ekers)\ **Post date:** [June 29, 2002, 9:55am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/12 "2002-06-29T09:55:04Z")
Well, I didn’t say _I_ thought the proof up one day while eating popcorn and watching _Simpsons_. It’s just one of the conceptually simplest proofs ever shown me during my otherwise wasted years in college. At this stage, the large primes aren’t really of any use except to display advancing computer tecnhology. I mean, c’mon, 2[sup]170141183460469231731687303715884105727[/sup] - 1 ? Aside from its appearance on Bill Gates’ bank statement, what good is it? ---
**Author:** ![bonzer](https://avatars.discourse-cdn.com/v4/letter/b/45deac/32.png) [@bonzer](https://boards.straightdope.com/u/bonzer)\ **Post date:** [June 29, 2002, 11:36am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/13 "2002-06-29T11:36:49Z")
Hmm, for the second time this week I find myself turning to Ribenboim’s _The Little Book of Big Primes_ (Springer-Verlag, 1991) in order to post about pi(x) … The OP’s question is actually of some interest, at least to number theorists. This is because the _prime counting function_ pi(x), the number of primes less than x, is one of the most important functions in the subject and people have devoted a lot of time to studying its properties. Most of that work has involved deep arguments devoted to extracting information about the function without having to actually count all the primes up to any particular value (as in the theorem posted by **Arnold** ), but such direct calculation of its value for different x is useful as a check. Now you might think that the best way to calculate it is just to determine all the primes between 1 and x and count them to find pi(x). But there’s a sneaky result from 1871 due to Meissel that shows that the function is such that you actually only need to know the primes up to x[sup]1/2[/sup] (if you also know the values of the function up to x[sup]2/3[/sup]). You exploit the known properties to extrapolate to higher values. Writing in 1991, Ribenboim quotes the largest known value of the function being for x = 4 x 10[sup]16[/sup], which suggests that at least all the primes up to about 2 x 10[sup]8[/sup] were known then. He also refers to the publication of a table of all of them up to 10[sup]8[/sup] back in 1914 and generally regards the problem as having become dull with the advent of computers, claiming that it’s faster to use the sieve of Eratosthenes to find such sequences of primes than look them up - as in the example posted by **perspective**. ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [June 29, 2002, 11:51am UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/14 "2002-06-29T11:51:45Z")
Large primes are very useful in cryptography, because of the difficulty of factorizing large numbers. Take two large primes p and q and form their product pq. You can publish the number pq since it will only allow people to send you encrypted messages. To unencrypt the message you would need to know the original primes p and q and this is very difficult. [This site](http://www.ercim.org/publication/Ercim_News/enw22/large-numbers.html) has a few details. [This one](http://home.ecn.ab.ca/~jsavard/crypto/publ05.htm) covers the subject in much more depth. [The Prime Pages](http://www.utm.edu/research/primes/) contain lots of information about prime numbers but not, as far as I can see, the answer to the OP. [This site](http://www.rsok.com/~jrm/printprimes.html) has various programs generating prime numbers. Still struggling with the OP question, though. The best I’ve got so far is a comment in Hardy & Wright, _An Introduction to the Theory of Numbers_ that the table of primes is complete up to 100,000,000. If this is still true the fourth link I gave gives the answer 99,999,989. However, the speed with which it gave the answer suggests that the record is now rather higher. ---
**Author:** ![ScarletSteve](https://avatars.discourse-cdn.com/v4/letter/s/59ef9b/32.png) [@ScarletSteve](https://boards.straightdope.com/u/ScarletSteve)\ **Post date:** [June 29, 2002, 12:16pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/15 "2002-06-29T12:16:14Z")
> [@](#): > > \*Originally posted by Jabba \* > \*\*Take two large primes p and q and form their product pq. You can publish the number pq since it will only allow people to send you encrypted messages. To unencrypt the message you would need to know the original primes p and q and this is very difficult. \*\* A bit out of my depth here, but what I don’t understand is that surely it is relativly simple to assemble a table of all the products of (large) primes. This could then quickly give you the original primes for any encrypted message and its published product. Unless large primes are kept secret (and I assume they aren’t, but they might always be filed next to those plans for cars that run on water 🙂 I’m not challenging what you say, Jabba, as I have seen this explanation before in seemingly authoritative texts, but just need it explaining further. ---
**Author:** ![Shade](https://avatars.discourse-cdn.com/v4/letter/s/2bfe46/32.png) [@Shade](https://boards.straightdope.com/u/Shade)\ **Post date:** [June 29, 2002, 12:23pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/16 "2002-06-29T12:23:31Z")
> [@](#): > > _Originally posted by Bryan Ekers \* > \*\*M+1 isn’t divisible by any of them. Therefore M+1 is a prime and larger than P_n\*. And if you add M+1 to your set of primes, you can generate and een larger prime, _ad infinitum_. > \*\* This is quite correct but for some reason I find it more satisfying to say ‘…hence M+1 is either prime or divisible by a prime not in the list, thus contradicting the list being complete’ perhaps because it is a more general statement that if the list are all prime then this is true, but M+1 being prime can only be deduced if they are the only primes. What the hell, I like yours. I’m using it from now on. ---
**Author:** ![jcgmoi](https://avatars.discourse-cdn.com/v4/letter/j/a9adbd/32.png) [@jcgmoi](https://boards.straightdope.com/u/jcgmoi)\ **Post date:** [June 29, 2002, 1:34pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/17 "2002-06-29T13:34:27Z")
**shade** , better stick to your original definition. 2_3_5_7_11_13 + 1 = 30031 = 59_509 ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [June 29, 2002, 2:56pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/18 "2002-06-29T14:56:50Z")
> [@](#): > > \*Originally posted by ScarletSteve \* > > A bit out of my depth here, but what I don’t understand is that surely it is relativly simple to assemble a table of all the products of (large) primes. This could then quickly give you the original primes for any encrypted message and its published product. Unless large primes are kept secret (and I assume they aren’t, but they might always be filed next to those plans for cars that run on water 🙂 > > I’m not challenging what you say, Jabba, as I have seen this explanation before in seemingly authoritative texts, but just need it explaining further. Large prime numbers can be closely guarded for precisely this reason. For example, from [Mathworld](http://mathworld.wolfram.com/PrimeNumber.html), > [@](#): > > Because of their importance in encryption algorithms such as RSA encryption, prime numbers can be important commercial commodities. In fact, R. Schlafly (1994) has obtained U.S. Patent 5,373,560 on the following two primes (expressed in hexadecimal notation) Unfortunately the two primes are gif files on the site, so I can’t copy and paste them ( which lessens the impact of my quote somewhat) but you can see them at the linked site. ---
**Author:** ![ScarletSteve](https://avatars.discourse-cdn.com/v4/letter/s/59ef9b/32.png) [@ScarletSteve](https://boards.straightdope.com/u/ScarletSteve)\ **Post date:** [June 29, 2002, 3:10pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/19 "2002-06-29T15:10:53Z")
Does that mean that there are a lot of ‘secret’ larger primes then? Presumably patenting doesn’t keep it secret, as you need to publish it so that people know what is patented. And could you really patent a number and prevent people form using it? ---
**Author:** ![Jabba](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@Jabba](https://boards.straightdope.com/u/Jabba)\ **Post date:** [June 29, 2002, 3:14pm UTC](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503/20 "2002-06-29T15:14:48Z")
Not necessarily larger: you might publish the largest one for the kudos and keep secret a number of smaller ones you find along the way. As you mention patenting has risks. You might decide simply to keep their existence secret. [Next page](https://boards.straightdope.com/t/largest-prime-number-in-the-sequence/116503.md?page=2)