That is genuinely fascinating.

I suppose that there actually are an infinite number of prime numbers, but since it takes longer and longer to find another one, the heat death of the Universe will occur before we can find too many more.

I love stuff like this. Thank you for posting.

But I believe quantum computing will aid the search for new primes by an order of magnitude, and has already.

I believe I read sometime this past year that these programs don't test each and every number successively. They sort of skip around and jump to random numbers to test them. So there could be many more lesser primes. (For some reason this bums me out.)

From the article:

... or they will be assigned to others. The faster/more productive your particular computer(s), the smaller the exponents you will be assigned. This way, the "leading edge" of all tested primes moves forward at a reasonably steady pace, despite being carried out on a wide variety of CPUs and GPUs by a variety of users around the world, some of whom never finish their assigned exponents for one reason or another.

The overall progress of GIMPS can be viewed at https://www.mersenne.org/primenet/ . A summary of milestones is at https://www.mersenne.org/report_milestones/ . Currently:


Progress toward next GIMPS milestones (last updated 2018-01-16 15:37:59 UTC, updates every hour)

All exponents below 42?120?083 have been tested and verified.
All exponents below 76?537?861 have been tested at least once.

Countdown to first time checking all exponents below 77 million: 46
Countdown to first time checking all exponents below M(77?232?917): 307 (211 available)
Countdown to first time checking all exponents below 78 million: 2?201 (944 available)
Countdown to first time checking all exponents below 79 million: 6?754 (5?003 available)

Countdown to verifying all tests below 43 million: 1?635 (1?240 available)
Countdown to verifying all tests below 44 million: 5?759 (4?265 available)

Countdown to verifying all tests below M(42?643?801): 600 (211 available)
Countdown to verifying all tests below M(43?112?609): 2?118
Countdown to verifying all tests below M(57?885?161): 232?306
Countdown to verifying all tests below M(74?207?281): 543?366
Countdown to verifying all tests below M(77?232?917): 600?230

As you can see, it will take a while to finish testing all primes less than the new discovery, and still longer to verify (double-check) them all, confirming there is no smaller prime.

The GIMPS rules used to much more permissive; they were tightened up because the lag between finding new primes and confirming all smaller composites was getting out of hand, with some members taking years to return results (been there, done that ).

Disclaimer: I am not one of the people in charge of GIMPS, PrimeNet, or GPUto72. I prefer to think of myself as just another exponent.

Some people are good at math, the rest of us are clueless.

You said, "As you can see, it will take a while to finish testing all primes less than the new discovery" Sorry, but I don't really think I'll ever be able to see it.

Thanks for trying to explain it all, it is just over my head but I am still intrigued by primes and I believe I will someday be able to solve the puzzle and also figure out how pi repeats/works. Seriously, thanks again for trying to explain it.

So, while there may be smaller Mersenne primes yet unknown, the process to eliminate that possibility is thorough, but a little slower than the (crowdsourced, hence *somewhat* random) search to discover new primes.

We already know there are no undiscovered Mersenne primes smaller than 2^76,537,861 - 1, a number of more than 23 million digits, and within a couple of years we will know whether there are any Mersenne primes smaller than the one in the OP.

A shortcut would be nice, and would also earn a lot of prize money.

They have to be a factor of 2. I would just think they would be easier to detect than just random odd numbers.

By the way can you help with something that I've never understood. Given a number such as "2^76,537,861 - 1" how do you get to 23 million digits? ^76,537,861, does calculating 2 to that power really give you 23 million select digits. It just seems the notation is too simple.

It's called a Lucas-Lehmer test, and it only works if the Mersenne number is prime. If the test fails, it does *not* tell you what any divisors of the Mersenne number are, only that some such must exist.

The special form of Mersenne numbers also makes "trial factoring" -- i.e., just trying one factor after another -- particularly fast. Trial factoring can be used to check for small factors before carrying out a Lucas-Lehmer test, which takes a *lot* of computer time. If trial factoring works, you don't need to do the LL test, but you have to get lucky for trial factoring to work. About ~60% of large exponents are successfully trial factored; the rest must be Lucas-Lehmer tested.

As to your second question -- yes, any integer (whole number) raised to an integer is exactly specified. Keep in mind that our normal notation for numbers is a power series, or sum of powers, just written in a compact form. For example, 2018 is just a compact notation for (2*10^3) + (0*10^2) + (1*10^1) + (8*10^0). Normally, we take the powers of 10 to be implied, just to keep things compact, and are so used to it we don't even think about it. 10 raised to the Nth power is represented in this ("base ten" ) notation as 1 followed by N zeroes. So we build a number (or strictly, a base ten represenation of a number) by adding together multiples of powers of ten. Given a general random number, that may be the best way to do it. But consider this: 10^4 = 10,000, so 10^4 - 1 = 9999, which is a precise number, written in two different ways. If you had a string of, say, 17123 "nine's", it would be inconvenient to write it all those digits, but you could still say it's 10^17123 - 1 -- in fact, it's easier to write it that way! So, for "special" numbers like Mersenne numbers which are very close to perfect powers, we just write them as perfect powers plus or minus a little difference -- one, in the case of Mersenne numbers.

(If it's not going too far, computers represent numbers internally in base two notation, so 2^ N - 1 is just a string of N one's in the computer's memory. That gives Mersenne numbers a special role in some types of computer applications -- Apple's QuickTime video compression technology, for example.)

You make it sound so obvious but it is so confusing to me. I will look at it again, I still don't get it at first reading. Thanks again for trying but I am just going to have to study your answers to get it. It just doesn't make sense to me. But I will try again, there must be some way to understand it, I simply have to really study it, but it just seems so confusing.

If say you are looking at 100,000 digits of pi, how do you reduce it to scientific notation and then when wanted expand it to all 100,000 digits. It just seems impossible to take 100,000 digits and notate them in a 10 digit exponential number.

Sorry, for being obtuse but I have just never figured this out. One more time if I have a number such as 34987654773890939980, how do I write that in scientific notation?

Thanks for considering this query!

A trillion is a special number because we've defined it to be precisely 10^12. Likewise many other powers of 10 (hundred, thousand, any power of 1000, and a Googol (10^100)). Most numbers, however, are not special in this sense.

Pi, for example apparently never forms any pattern of digits, in base ten, or in any integer, or even rational, base. If you want to express pi to a very high degree of accuracy you just pick a base -- humans pick base 10, computers base 2 -- and start writing out digits to whatever accuracy you need. For most purposes, even precise engineering calculations, 3-5 digits of accuracy is enough. The only shorthand we have for exactly pi is, well, "pi" (or ? ).

If we want to express 34987654773890939980 accurately, so that the error is less than one, you have to write out all the digits, whether in normal or scientific notation. If it's OK to express it *approximately*, you could write 3.5 x 10^19, or 3.50 x 10^19, or 3.499 x 10^19, or ... 3.4987654773890939980 x 10^19, each version being more precise than the previous one. Again, for most practical, real-world purposes, the first (aka most significant) 3-5 digits will do.

(This concept of significant digits, or significant figures, is one that we spend quite a lot of time explaining to our students in intro chemistry courses, or really, any course that at least occasionally relies on numerical calculations. Some people seem to "get it" almost intuitively, many others struggle with it, and are still making basic errors after two semester of General Chemistry. So I've definitely seen a range of aptitudes in this area. Like many in the sciences, I tend to believe that electronic calculators add somewhat to the problem, since they usually give every answer out to more places than can possibly be significant, but many people don't realize the difference -- 2.49999999999999 is not necessarily more accurate than 2.5, particularly if you got it by taking the square root of 6.25. Calculators crank out all those digits so precisely that people don't realize the result must be approximate if the input was approximate, and are so easy to use that anyone can carry out "hard" arithmetic, but don't realize that they can do inaccurate calculations just as easily. The user has to know the difference.)

If you're wanting to answer a question such as "is this integer a multiple of three?" then you need to need to know all the digits. If you ask a question such as "is 3.499 x 10^19 a multiple of three?" then you have to say "I don't know, because you've only given me an approximate number." If the number is not an exact integer, remainders are a meaningless concept. Much of the work in the theory of integers is based on the concept of divisibility, which is usually discussed in the form of zero or nonzero remainders, or residues, as they are termed in modular arithmetic. This is *part* of the reason why so much work has been done on special numbers which can be represented as a very short (one or two term) power series. Mersenne numbers are a subclass of a type of numbers known as repunits, which are a subclass of numbers which can be represented as a difference of two powers: (a^m - b^n). You can draw many conclusions about the factors of such numbers, even without knowing further details -- for example, (a^m - b^n) must always be divisible by (a-b). Setting a = 2 and b=1 gives you the special case of Mersenne numbers, which must all be divisible by (2-1), or 1 -- so you can't find any nontrivial factors by this rule. You can also prove that (a^m - 1) is always divisible by (a-1), so that's why a=2 is a special case -- any larger value of a will give you a composite number, but a=2 again is only guaranteed to be divisible by 1. Further, if m is composite -- say m = c*d -- then it can be shown that (2^m-1) is divisible by (2^c-1) and (2^d-1). If m is a prime number -- 2^p - 1 -- then you can't predict *any* nontrivial factors, but must test each prime-exponent Mersenne for divisibility by trial-and-error, or perform a Lucas-Lehmer test (which is only for prime-exponent Mersennes).

That was more than you asked, but it seemed appropriate to add a little about why Mersennes are "special" in the context of remainders/residues.