Sat Jan 6, 2018, 02:10 AM
eppur_se_muova (28,229 posts)
GIMPS Project Discovers Largest Known Prime Number: 2**77,232,9171
GIMPS Project Discovers
Largest Known Prime Number: 2^77,232,9171 RALEIGH, NC., January 3, 2018  The Great Internet Mersenne Prime Search (GIMPS) has discovered the largest known prime number, 2^77,232,9171, having 23,249,425 digits. A computer volunteered by Jonathan Pace made the find on December 26, 2017. Jonathan is one of thousands of volunteers using free GIMPS software available at www.mersenne.org/download/. The new prime number, also known as M77232917, is calculated by multiplying together 77,232,917 twos, and then subtracting one. It is nearly one million digits larger than the previous record prime number, in a special class of extremely rare prime numbers known as Mersenne primes. It is only the 50th known Mersenne prime ever discovered, each increasingly difficult to find. Mersenne primes were named for the French monk Marin Mersenne, who studied these numbers more than 350 years ago. GIMPS, founded in 1996, has discovered the last 16 Mersenne primes. Volunteers download a free program to search for these primes, with a cash award offered to anyone lucky enough to find a new prime. Prof. Chris Caldwell maintains an authoritative web site on the largest known primes, and has an excellent history of Mersenne primes. The primality proof took six days of nonstop computing on a PC with an Intel i56600 CPU. To prove there were no errors in the prime discovery process, the new prime was independently verified using four different programs on four different hardware configurations. Aaron Blosser verified it using Prime95 on an Intel Xeon server in 37 hours. David Stanfill verified it using gpuOwL on an AMD RX Vega 64 GPU in 34 hours. Andreas Höglund verified the prime using CUDALucas running on NVidia Titan Black GPU in 73 hours. Ernst Mayer also verified it using his own program Mlucas on 32core Xeon server in 82 hours. Andreas Höglund also confirmed using Mlucas running on an Amazon AWS instance in 65 hours. Jonathan Pace is a 51year old Electrical Engineer living in Germantown, Tennessee. Perseverance has finally paid off for Jon  he has been hunting for big primes with GIMPS for over 14 years. The discovery is eligible for a $3,000 GIMPS research discovery award. GIMPS Prime95 client software was developed by founder George Woltman. Scott Kurowski wrote the PrimeNet system software that coordinates GIMPS' computers. Aaron Blosser is now the system administrator, upgrading and maintaining PrimeNet as needed. Volunteers have a chance to earn research discovery awards of $3,000 or $50,000 if their computer discovers a new Mersenne prime. GIMPS' next major goal is to win the $150,000 award administered by the Electronic Frontier Foundation offered for finding a 100 million digit prime number. Credit for this prime goes not only to Jonathan Pace for running the Prime95 software, Woltman for writing the software, Kurowski and Blosser for their work on the Primenet server, but also the thousands of GIMPS volunteers that sifted through millions of nonprime candidates. In recognition of all the above people, official credit for this discovery goes to "J. Pace, G. Woltman, S. Kurowski, A. Blosser, et al." About Mersenne.org's Great Internet Mersenne Prime Search The Great Internet Mersenne Prime Search (GIMPS) was formed in January 1996 by George Woltman to discover new world record size Mersenne primes. In 1997 Scott Kurowski enabled GIMPS to automatically harness the power of thousands of ordinary computers to search for these "needles in a haystack". Most GIMPS members join the search for the thrill of possibly discovering a recordsetting, rare, and historic new Mersenne prime. The search for more Mersenne primes is already under way. There may be smaller, as yet undiscovered Mersenne primes, and there almost certainly are larger Mersenne primes waiting to be found. Anyone with a reasonably powerful PC can join GIMPS and become a big prime hunter, and possibly earn a cash research discovery award. All the necessary software can be downloaded for free at www.mersenne.org/download/. GIMPS is organized as Mersenne Research, Inc., a 501(c)(3) science research charity. Additional information may be found at www.mersenneforum.org and www.mersenne.org; donations are welcome. For More Information on Mersenne Primes Prime numbers have long fascinated both amateur and professional mathematicians. An integer greater than one is called a prime number if its only divisors are one and itself. The first prime numbers are 2, 3, 5, 7, 11, etc. For example, the number 10 is not prime because it is divisible by 2 and 5. A Mersenne prime is a prime number of the form 2P1. The first Mersenne primes are 3, 7, 31, and 127 corresponding to P = 2, 3, 5, and 7 respectively. There are now 50 known Mersenne primes. Mersenne primes have been central to number theory since they were first discussed by Euclid about 350 BC. The man whose name they now bear, the French monk Marin Mersenne (15881648), made a famous conjecture on which values of P would yield a prime. It took 300 years and several important discoveries in mathematics to settle his conjecture. At present there are few practical uses for this new large prime, prompting some to ask "why search for these large primes"? Those same doubts existed a few decades ago until important cryptography algorithms were developed based on prime numbers. For seven more good reasons to search for large prime numbers, see here. Previous GIMPS Mersenne prime discoveries were made by members in various countries. In January 2016, Curtis Cooper et al. discovered the 49th known Mersenne prime in the U.S. In January 2013, Curtis Cooper et al. discovered the 48th known Mersenne prime in the U.S. In April 2009, Odd Magnar Strindmo et al. discovered the 47th known Mersenne prime in Norway. In September 2008, HansMichael Elvenich et al. discovered the 46th known Mersenne prime in Germany. In August 2008, Edson Smith et al. discovered the 45th known Mersenne prime in the U.S. In September 2006, Curtis Cooper and Steven Boone et al. discovered the 44th known Mersenne prime in the U.S. In December 2005, Curtis Cooper and Steven Boone et al. discovered the 43rd known Mersenne prime in the U.S. In February 2005, Dr. Martin Nowak et al. discovered the 42nd known Mersenne prime in Germany. In May 2004, Josh Findley et al. discovered the 41st known Mersenne prime in the U.S. In November 2003, Michael Shafer et al. discovered the 40th known Mersenne prime in the U.S. In November 2001, Michael Cameron et al. discovered the 39th Mersenne prime in Canada. In June 1999, Nayan Hajratwala et al. discovered the 38th Mersenne prime in the U.S. In January 1998, Roland Clarkson et al. discovered the 37th Mersenne prime in the U.S. In August 1997, Gordon Spence et al. discovered the 36th Mersenne prime in the U.K. In November 1996, Joel Armengaud et al. discovered the 35th Mersenne prime in France. Euclid proved that every Mersenne prime generates a perfect number. A perfect number is one whose proper divisors add up to the number itself. The smallest perfect number is 6 = 1 + 2 + 3 and the second perfect number is 28 = 1 + 2 + 4 + 7 + 14. Euler (17071783) proved that all even perfect numbers come from Mersenne primes. The newly discovered perfect number is 2^77,232,916 x (2^77,232,9171). This number is over 46 million digits long! It is still unknown if any odd perfect numbers exist. There is a unique history to the arithmetic algorithms underlying the GIMPS project. The programs that found the recent big Mersenne primes are based on a special algorithm. In the early 1990's, the late Richard Crandall, Apple Distinguished Scientist, discovered ways to double the speed of what are called convolutions  essentially big multiplication operations. The method is applicable not only to prime searching but other aspects of computation. During that work he also patented the Fast Elliptic Encryption system, now owned by Apple Computer, which uses Mersenne primes to quickly encrypt and decrypt messages. George Woltman implemented Crandall's algorithm in assembly language, thereby producing a primesearch program of unprecedented efficiency, and that work led to the successful GIMPS project. School teachers from elementary through highschool grades have used GIMPS to get their students excited about mathematics. Students who run the free software are contributing to mathematical research. David Stanfill's and Ernst Mayer's verification computations for this discovery was donated by Squirrels LLC (http://www.airsquirrels.com) which services K12 education and other customers. [1] Science (American Association for the Advancement of Science), May 6, 2005 p810. *** press release, see https://www.mersenne.org/primes/press/M77232917.html The ** and ^ above represent the powering operator; HTML superscripts are no longer supported in DU3.

12 replies, 737 views
12 replies  Author  Time  Post 
GIMPS Project Discovers Largest Known Prime Number: 2**77,232,9171 (Original post) 
eppur_se_muova  Jan 2018  OP 
PoindexterOglethorpe  Jan 2018  #1  
AnonC  Jan 2018  #2  
gvstn  Jan 2018  #3  
eppur_se_muova  Jan 2018  #5  
gvstn  Jan 2018  #6  
eppur_se_muova  Jan 2018  #7  
gvstn  Jan 2018  #8  
eppur_se_muova  Jan 2018  #9  
gvstn  Jan 2018  #10  
gvstn  Jan 2018  #11  
eppur_se_muova  Jan 2018  #12  
LastLiberal in PalmSprings  Jan 2018  #4 
Response to eppur_se_muova (Original post)
Sat Jan 6, 2018, 02:33 AM
PoindexterOglethorpe (5,940 posts)
1. Oh, my.
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. 
Response to PoindexterOglethorpe (Reply #1)
Sat Jan 6, 2018, 05:56 AM
AnonC (445 posts)
2. Agreed its fascinating.
But I believe quantum computing will aid the search for new primes by an order of magnitude, and has already.

Response to PoindexterOglethorpe (Reply #1)
Mon Jan 8, 2018, 04:02 PM
gvstn (2,805 posts)
3. Just wanted to mention.
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: The search for more Mersenne primes is already under way. There may be smaller, as yet undiscovered Mersenne primes, and there almost certainly are larger Mersenne primes waiting to be found. 
Response to gvstn (Reply #3)
Tue Jan 16, 2018, 12:35 PM
eppur_se_muova (28,229 posts)
5. Exponents are assigned to various users, who must complete them within a certain length of time, ...
... 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 20180116 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 (doublecheck) 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. 
Response to eppur_se_muova (Reply #5)
Tue Jan 16, 2018, 01:06 PM
gvstn (2,805 posts)
6. I think I understand about one tenth of your explanation.
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. 
Response to gvstn (Reply #6)
Tue Jan 16, 2018, 03:01 PM
eppur_se_muova (28,229 posts)
7. Well, the bottom line is that the whole process is being supervised and managed.
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. 
Response to eppur_se_muova (Reply #7)
Tue Jan 16, 2018, 06:50 PM
gvstn (2,805 posts)
8. I would think Mersenne primes would be the easiest to detect.
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. 
Response to gvstn (Reply #8)
Tue Jan 16, 2018, 10:07 PM
eppur_se_muova (28,229 posts)
9. They are ! There is a special test that applies only to Mersenne numbers.
It's called a LucasLehmer 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 LucasLehmer 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 LucasLehmer 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.) 
Response to eppur_se_muova (Reply #9)
Wed Jan 17, 2018, 12:02 PM
gvstn (2,805 posts)
10. I've got to think about this.
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.

Response to eppur_se_muova (Reply #9)
Sun Jan 21, 2018, 02:53 PM
gvstn (2,805 posts)
11. Thanks again but I still haven't gotten it.
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! 
Response to gvstn (Reply #11)
Sun Jan 21, 2018, 03:56 PM
eppur_se_muova (28,229 posts)
12. Mersenne numbers are special in a way that allows them to be written compactly ...
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, 35 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, realworld purposes, the first (aka most significant) 35 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 (ab). Setting a = 2 and b=1 gives you the special case of Mersenne numbers, which must all be divisible by (21), 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 (a1), 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^m1) is divisible by (2^c1) and (2^d1). If m is a prime number  2^p  1  then you can't predict *any* nontrivial factors, but must test each primeexponent Mersenne for divisibility by trialanderror, or perform a LucasLehmer test (which is only for primeexponent 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. 
Response to eppur_se_muova (Original post)
Tue Jan 16, 2018, 03:51 AM
LastLiberal in PalmSprings (6,984 posts)