Over the past few months, I have been inundated with tweets about the largest prime number ever found. That number, according to Nature News, is $latex 2^{57,885,161}-1$. This is certainly a very large prime number and one would think that we would need a supercomputer to find a prime number larger than this one. In fact, Nature mentions that there are infinitely many prime numbers, but the powerful prime number theorem doesn’t tell us how to find them!

Well, I am here to tell you of the discovery of the new largest prime number ever found, which I will call $latex P_{euclid}$. Here it is:

$latex P_{euclid} = 2cdot 3cdot 5cdot 7cdot 11 cdot cdots cdot (2^{57,885,161}-1) +1.$

This number, the product of all prime numbers known so far plus one, is so large that I can’t even write it down on this blog post. But it is certainly (proof left as an exercise…!) a prime number (see Problem 4 in The allure of elegance) and definitely larger than the one getting all the hype. Finally, I will be getting published in Nature!

In the meantime, if you are looking for a real challenge, calculate how many digits my prime number has in base 10. Whoever gets it right (within an order of magnitude), will be my co-author in the shortest Nature paper ever written.

*Update 2: I read somewhere that in order to get attention to your blog posts, you should sprinkle them with grammatical errors and let the commenters do the rest for you. I wish I was mastermind-y enough to engineer this post in this fashion. Instead, I get the feeling that someone will run a primality test on $latex P_{euclid}$ just to prove me wrong. Well, what are you waiting for? In the meantime, another challenge: What is the smallest number (ballpark it using Prime Number Theorem) of primes we need to multiply together before adding one, in order to have a number with a larger prime factor than $latex 2^{57,885,161}-1$?*

*Update: The number $latex P_{euclid}$ given above may not be prime itself, as pointed out quickly by Steve Flammia, Georg and Graeme Smith. But, it does contain within it the new largest prime number ever known, which may be the number itself. Now, if only we had a quantum computer to factor numbers quickly…Wait, wasn’t there a polynomial time primality test?*

*Note: The number mentioned is the largest known Mersenne prime. That Mersenne primes are crazy hard to find is an awesome problem in number theory.*

sflammiaMarch 27, 2013 at 1:43 pmUmmm, I don’t see why that number is prime. N!+1 isn’t prime in general. Consider 6!+1 = 7*103. Is there a special property of Mersenne primes which makes the statement true?

spirosMarch 27, 2013 at 1:44 pmProduct of primes only.

GeorgMarch 27, 2013 at 1:48 pmWhile your P_{Euclid} certainly has a prime factor larger than 2^{57,588,161}-1, it need not itself be prime. For example, 2*3*5*7*11*13+1 = 30,031 = 59 * 509.

spirosMarch 27, 2013 at 2:07 pmThanks for catching this Georg! Now I feel like Merlin, trying to convince Arthur that the number is prime…

sflammiaMarch 27, 2013 at 1:51 pmSorry, I misspoke above, but the point still stands. Consider the “primorial” function P(n) which returns the product of the first n prime numbers. Then P(n)+1 is not in general prime. P(6)+1 = 30031=59*509.

sflammiaMarch 27, 2013 at 1:53 pmDamn, Georg beat me to it while I was opening Wolfram Alpha. ðŸ™‚

GraemeMarch 27, 2013 at 1:52 pmSpiros, the product of the first n primes plus 1 doesn’t have to be prime itself. It’s just relatively prime with all of the first n primes. Consider: 2*3*5*7*11*13 + 1 = 30031, which is divisible by 59. So, while 2^{57885161} – 1 is the largest known Mersenne prime, it’s also the largest known prime. Actually, the 10 largest known primes are Mersennes (11th isn’t).

spirosMarch 27, 2013 at 1:54 pmI should have said contains a larger prime as a divisor. I will update the post. Thanks!

GraemeMarch 27, 2013 at 2:07 pmNow all you have to do is factor that beast and you’ve got your new largest prime!

Ross ChurchleyMarch 27, 2013 at 2:11 pmI think you’ve fallen into a common trap here. Euclid’s proof only tells you that the product of a list of primes plus one is not divisible by anything on the list. It doesn’t have to be prime itself, as long as its prime factors are not on the list (for example, 2*3*5*7*11*13+1 is divisible by 59). Your P_euclid definitely contains a bigger prime factor â€” the real challenge is figuring out what that is!

Curious GeorgeMarch 27, 2013 at 6:25 pmYour Euclid number is not a product of the first N primes, you are cherry-picking. For example, 2*7+1 is not a prime. It even has a divisor smaller than 7.

spirosMarch 27, 2013 at 6:27 pmCan you clarify your comment? It is defined as the product of the first n primes plus one.

JonathanMarch 27, 2013 at 6:59 pmTechnically, you defined P_euclid as “the product of all prime numbers known so far plus one”, which misses out on unknown primes less than 2^{57,588,161}-1.

spirosMarch 27, 2013 at 7:02 pmInteresting and valid point! I don’t even remember saying “known primes”, but either way I wonder if there are in fact primes smaller than the one listed which we don’t know about… Again, great point.

AnzelMarch 27, 2013 at 7:19 pmI’m certain there are plenty (a understatement) of primes we don’t know about below this value, since much of the search for large primes has focused entirely on Mersenne primes (see http://primes.utm.edu/largest.html)

Quote: “Why Mersennes? Because the way the largest numbers N are proven prime is based on the factorizations of either N+1 or N-1, and for Mersennes the factorization of N+1 is as trivial as possible (a power of two).”

AnzelMarch 27, 2013 at 7:24 pmAlso, check the link for a list of the largest known Primorial primes, which are primes of the type 2*3*5*7*…*p_n $pm$ 1.

spirosMarch 27, 2013 at 7:27 pmThanks Anzel. The link is very interesting. Primorial primes have a name after all… Now I want to know if there is a pattern for which primorial numbers are prime!

AnzelMarch 27, 2013 at 10:34 pmAlso, this may have some errors but here’s a rough estimate of the number of digits of P_euclid

log = log10

M_48 is the newest prime (48th? Mersenne)

# digits = log(P_{euclid})

approx log (product of all primes up to M_{48})

= sum of all primes up to M_{48}log(p_i)

So as a first estimate, we can ask how many primes there are with 1 digit, 2 digits, 3 digits… up to log(M_{48})

~ 1*(pi(10)-pi(1)) + 2*(pi(100)-pi(11)) + 3*(pi(1000) – pi(101)) +…

Turning this into an integral

~ int_epsilon^log(M_{48}) x*(pi(10^x) – pi(10^{x-1})*dx

Note the lower integral is kind of irrelevant (since the values will be small).

Using the most basic approximation that pi(x) ~ x/ln(x), the integral solves to

(9/10)10^log(M_{48})/ln(10)^2 + (1/log(10))*Ei ((log M_48-1) ln10)

Ei(u) ~ exp(u)/u for large u

~ (9/10)*M_48/ln(10)^2 + (1/10)*M_48/(ln10)^2/(log(M_48)-1)

~ (9/10)*M_48/ln(10)^2

~0.17*M_48 = 0.17*10^(log(2)*57885161)

# of digits ~ 1E17425169 or p_euclid ~ 10^M_48

Then having gone through all of that, I found http://www.ams.org/journals/mcom/2002-71-237/S0025-5718-01-01315-1/S0025-5718-01-01315-1.pdf which states that ln p# ~ p, and so the real answer is about .43*M_48. Oh well, close enough.

spirosMarch 27, 2013 at 10:52 pmThanks for doing all the hard work Paul! I guess I was right about one thing: this number is a massive beast that wouldn’t fit inside this blog post (10^{17.4 million} digits would require many universes to lend me their WordPress space). Now, what is the last digit of P_{euclid}?

AnzelMarch 27, 2013 at 11:18 pmWhoops, I did the Riemann sum incorrectly. The real answer is

# digits ~ $latex int^M x d/dx pi (10^x) dx$

Which simplifies to the correct answer. (let $latex pi (x)$ be x/ln(x)).

The final digit is 7. Try and prove me wrong.

spirosMarch 27, 2013 at 11:19 pmThe number 2*3*5*7… ends in which digit? Then add 1.

AnzelMarch 27, 2013 at 11:42 pmOh wait, the final digit is 1, because of the 2*5.

spirosMarch 27, 2013 at 11:45 pmNicely done! What about the 2nd to last digit?

AnzelMarch 28, 2013 at 12:03 amOne of 1, 3, 7, or 9 (otherwise there would be two factors of 2 or 5), beyond that I don’t believe there’s a clear pattern.

spirosMarch 28, 2013 at 12:10 amThe answer is 7. Try to prove me wrong ðŸ™‚

AnzelMarch 28, 2013 at 1:20 amI wouldn’t even try, 7 is a great number, perfect for all occasions formal and casual.

What’s the last digit when you’re working in base 9?

Lubos MotlMarch 28, 2013 at 7:18 amDear Spiros,

I used to use all the Linux computers in the physics high-energy theory department to run the very same software to find the Mersenne primes – an enthusiasm for this particular question I no longer quite understand – and as a result, I can assure you of many things, for example that the number 2^{57,885,161} – 1 definitely *is* the largest known prime, not only the largest known Mersenne prime.

Others have explained to you why your “Euclid” number almost certainly isn’t a prime. But there’s a subtler point about which you’re totally wrong as well. A note of yours at the end says:

Note: The number mentioned is the largest known Mersenne prime. That Mersenne primes are crazy hard to find is an awesome problem in number theory.

But Spiros, this is a complete misunderstanding of the role of Mersenne primes among all primes. The Mersenne primes are, on the contrary, the *easiest* large primes to be looked for! That’s partly why the Mersenne prime project exists: it’s the search for the largest known prime at the same moment. The largest known Mersenne prime has been the largest known prime at the same moment for quite some time, without an interruption!

Finally, if this text of yours was meant as a real claim and not just a self-evident artificial error meant to build traffic, and if the “correction” was a real correction, then I must say that it is a very lame attempt to mask your previous argument’s lethal error. Of course that a random number that is incredibly larger than the currently largest known prime will contain some very large prime factors. But so will all other random very large numbers such as 10^{10^{100}}+1.

If you pick the “product of all primes up to the largest one plus one”, you only guarantee that this prescription isn’t divisible by any primes smaller than or equal to the currently largest known prime (most of them are unknown – it’s unknown whether the smaller primes than the largest number prime are prime or not, of course). But this is a negligible fraction of the tests one has to run in order to check whether a large number is a prime. Your “Euclid” number is a number of the sort 10^{10^{10,000,000}} and the number of its potential prime divisors is pretty much a number of the same sort, 10^{10^{10,000,000}}. But your form has only eliminated 10^{10,000,000} or so candidates, a hierarchically exponentially tiny fraction of the tests!

So e.g. my claim that there is a larger prime number and it may be obtained as a factor of 10^{10^{100}}+1, or any large number with a not-obvious complete factorization, is exactly “as good” as your claim about the Euclid number. The large number in the sentence may be replaced by any comparably large number. However, this prescription – the number is a factor of an even larger number – that’s what deserves the label of the “crazy hard problem”, unlike the problem to find a Mersenne prime. That’s why cryptographic algorithms are built on the impossibility to find primes p,q if one is given p*q in a realistic time!

If your text is serious, I must say that pretty much all the far-reaching messages of it, much like the main technical claim, is incorrect. It’s still brave that you discussed it because such things should be discussed and should be more widely known, at least in the broader math-trained public, but your contribution towards this goal was just a contribution of a provoking sequence of errors. ðŸ˜‰

Cheers

LM

spirosMarch 28, 2013 at 8:17 amDear Lubos,

Indeed, the post was meant to be a provocative attempt to shed more light on the search for large prime numbers, following the previous great post about cryptography. Fortunately, I made a grave mistake about the consequences of Euclid’s algorithm and something interesting happened: I received comments that were far more informative and engaging than the post itself. I learned about Primorial primes, that there are huge gaps in our knowledge of primes, that Mersenne primes are really difficult to find but also the easiest targets when looking for large primes and that you once spent your days looking for them with a cluster of Unix machines.

The teacher became the student again. Not bad for a lame little post.

Lubos MotlMarch 28, 2013 at 10:11 amIt’s a great success then, Spiros. ðŸ˜‰ You may want to run a text about a theory of everything, maybe it will lead to a discussion that will complete this task.

spirosMarch 28, 2013 at 10:21 amI don’t know if we could get a theory of everything out of blog comments, but we may attract people who have a theory for everything.

Lubos MotlMarch 28, 2013 at 10:23 amIncidentally, you’re into algorithms, sort of, so you may want to try to understand the Lucas-Lehmer test

http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test

that is used (along with some other test, to optimize the timing) to decide whether the Mersenne numbers are primes. Of course, the first thing to do is to notice that for 2^p-1 to be prime, p itself has to be a prime: for p=KL, 2^K-1 would be a divisor of 2^p-1.

I once understood why this test works but I forgot it and won’t study it again today. At any rate, it’s a special clever structure, a special algorithm, and this extra structure makes it easier, not harder, to decide about the primarily of the Mersenne numbers.

Just imagine how amazing it is that we may check whether a number with tens of millions of digits is a prime. Normally, by brute force, we would need to check all potential divisors up to sqrt(candidate), i.e. also so many candidates that the number of these candidates is also a number with tens of millions of digits (well, one half of the original one).

One clearly can’t make that many operations: when the brute force is the only recipe, i.e. when one talks about “generic” candidates for primes, they could have at most dozens of digits if you want the calculation to take a shorter time than the time that remains for the Sun to go red giant. ðŸ˜‰ But for the Mersenne primes, we’re remarkably able to decide about the primality of numbers that have tens of millions (not just hundreds!) of digits. Isn’t it amazing? To a certain extent, the Mersenne primes are “semi-constructive”: we may pretty much generate large primes of this sort while the remaining work to be done is vastly smaller than the verification of primality for a generic number.

So to a limited extent, the Mersenne primes are exactly playing the role you wanted to assign to the Euclid prime – except that the Mersenne numbers that pass the Lucas-Lehmer tests are really primes while your Euclid prime is not. ðŸ˜‰

LM

spirosMarch 28, 2013 at 10:27 amCool stuff! I will check out the primality test you link to. I have been wondering why it is so much easier to check primality of Mersenne primes…

reader01March 29, 2013 at 1:55 amI think that quantum computer will give us the solution about biggest prime number

reader01March 29, 2013 at 2:19 amMaybe Shore algorithm is the key for solution. Mathematicaly derived prime number from analyzed Shore algorithm will lead us to it.

reader01March 29, 2013 at 2:52 amProbably we should start with Shore algorithm applied to infinity-1??

Project Euler Problem# 5 solution in C++ | Khuram AliMarch 30, 2013 at 1:23 pm[…] Largest prime number found! (quantumfrontiers.com) […]

Elto DesukaneSeptember 24, 2013 at 10:04 pmGreat Internet Mersenne Prime Search, PrimeNet (v5.0)

GIMPS Milestones Report

January 25, 2013: Prime M(57885161) discovered!!

http://www.mersenne.org/report_milestones/default.php

mahi khannaAugust 15, 2014 at 7:44 amI have got the next largest prime number this year. tell me what should I do next.