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 ?
Searched for “largest prime number” on Google. First entry is this 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.
I’ll bet you $5.00 that 2^13466917 + 13 is also prime.
Sadly, we don’t know all prime numbers less than (2^13466917)-1. As this page 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.
Damn you, submit button! The number of primes <= x can be approximated using the prime number theorem:
pi(x) ~ x / ln (x)
andy_fl: Do not think we will ever know what the largest prime number is. The set of primes is infinite
Prove it.
Proving it is easy.
Assume the set of Primes is finite, consisting of {P1, P2, P3, … Pn}
Now imagine a number, M, which is equal to P1 x P2 x P3 x … Pn, 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 Pn. 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.
“you can generate an even larger prime”, rather.
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
Lots of other cool links for prime questions there.
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.
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?
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.
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 has a few details. This one covers the subject in much more depth.
The Prime Pages contain lots of information about prime numbers but not, as far as I can see, the answer to the OP.
This site 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.
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.
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.
shade, better stick to your original definition.
23571113 + 1 = 30031 = 59509
Large prime numbers can be closely guarded for precisely this reason. For example, from Mathworld,
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.
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?
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.