Double Maths First Thing is part of Colin’s fight against the forces of tedium.
Hello, and welcome to Double Maths First Thing! My name is Colin and I am a mathematician, on a mission to spread joy and delight in maths.
More from me
I promise not to make this whole thing about me, but if I’ve got a blog post about something I find delightful, it would be rude not to share it. Here’s a link that took me a long time to make about the relationship between the binomial expansion and the binomial distribution. The clue’s in the name, right?
New Largest Known Prime!(?)
I am decidedly ambivalent about finding larger and larger Mersenne primes. I feel like some of those involved in the hunt are in it for the money, the mersennaries. Even if it’s been six years since the last one, the announcement that there’s a new one is not one that thrills me. I think throwing more compute at the same problem is of limited use. However, it has reminded me about the Lucas-Lehmer test, which is a very nice piece of maths that happens to coincide with the structure of computers, making it efficient (although still lengthy) to calculate.
Somewhere deep in the list of tabs that seemed like a good idea to open, I found instructions for making a giant windball. It uses some sort of construction kit called makedo, but I’d be surprised if you couldn’t find some butterfly pins and spare cardboard.
I was surprised by a result, which is always a nice feeling: if you’re thinking about balls (settle down back there), you’d expect to see \( \pi \) show up. Finding \( e \) was not on my bingo card.
Stretching the theme still further, I hadn’t heard of Pappus’s centroid theorem(s), which you could use to work out the volume of a sphere (see! There is a link!) — they’re reasonably obvious once you think about them a little, but it’s still a nice way to approach surfaces and volumes of revolution.
Other nice things!
From Reddit, probably to be filed under “absurd but also very impressive”: a computer cuber broke a world record. Not just any world record, but the record for a 121-by-121-by-121 cube. By 69 hours. My understanding is that a 121-cube is just like a 5-cube, only more so — but still, the concentration and dedication you’d need to do that… chapeau! Oh, and they say this is the fifth-largest cube ever solved by a human.
Over on the platform-still-referred-to-as-Twitter-by-everyone-sensible, David K Butler has an interesting way to look at addition and multiplication using parallel and intersecting lines (respectively). I’m always up for a new thing to add to my mental models!
In podcast news, I am given to believe that Sam Hansen is at it again. I’m not sure they ever stopped, honestly; Sam and Sadie Witkowski now co-host Carry The Two, recently with a theme of elections and representation. It’s almost enough to get me to the gym so I can listen to it in peace. Almost.
And — if you’re quick about it — you might be able to subscribe to the Finite Group in time for their first anniversary livestream.
In the meantime, if you have friends and/or colleagues who would enjoy Double Maths First Thing, do send them the link to sign up — they’ll be very welcome here.
That’s all for this week! If there’s something I should know about, you can find me on Mathstodon as @icecolbeveridge, or at my personal website. You can also just reply to this email if there’s something I should be aware of.
This article originally attributed the last Mersenne prime found by hand to Leonhard Euler. It was Édouard Lucas. So, that’s what the title is about. We also only realised after publication that there’s a wordplay in the title that only works if you say Euler wrong. The proofreaders apologise.
There is an ongoing quest in mathematics to find larger and larger prime numbers. Since the primes go on forever, there is no single largest one, but every day around the world computers are churning to find a new record holder.
This project was inspired by a Numberphile video about how mathematicians find enormous prime numbers. The goal is to find a large prime number ourselves, one that took mathematicians over 2,000 years to find. The record for the largest known prime has since been broken since that video was released; the largest known prime as of May 2021 is
\[ M_{82,589,933} = 2^{82,589,933} – 1 \]
If you were to write the number down it would be longer than the entire text of the Harry Potter series. We won’t find any prime numbers nearly that big, but we can try to find one too big to fit in a single tweet.
I don’t believe anyone has ever read the largest prime number from beginning to end.
2,000 years of math in 10 lines of Python
Mathematicians have been trying to find progressively larger prime numbers for several thousand years – the University of Tennessee at Martin has a great introduction to the topic. While the current record holders are found with computers, these techniques were once done by hand. The last time a human set the record for calculating the largest known prime was done by Édouard Luca in 1876 when he proved that $M_{127}$ is prime. Lucas’ record stood for 76 years until 1952 when a computer finally found a larger prime number. Since then all records have been set with the help of computers. In 10 lines of Python code, we will prove Lucas was right and find a bigger prime, surpassing more than 2,000 years of mathematical history.
With pen and paper, Lucas showed that $M_{127}$ is prime.
$M_{82,589,933}$ was found by a worldwide computer search called the Greater Internet Mersenne Prime Search, known as GIMPS. GIMPS works by picking a number that might be prime and testing it using a massive network of volunteered computers. By breaking the rather difficult question “Is this number prime?” into smaller pieces each machine in the network can work on a chunk of the problem they can handle, then report its results. This massively parallelized structure allows their network of more than two million computers to tackle prime numbers far larger than any single machine could handle.
GIMPS runs several tests on each candidate number before running the most conclusive, and slowest, test to see if a candidate number is indeed prime. These initial screens, which include trial division and Pollard’s P-1 method, can quickly show if a candidate is composite, so they can eliminate candidates, but cannot prove a number is prime. Once a candidate passes all the early rounds it’s time for the conclusive test. Until 2018, their conclusive test was the Lucas-Lehmer Primality test. The Lucas-Lehmer test is a definitive method to prove whether or not a number is prime and the one we’ll be focusing on. In 2018, GIMPs did change their final test to the Fermat Probable Prime test since it could be implemented with a lower chance of hardware error. They improved the method again in 2020 when new work by Krzysztof Pietrzak eliminated the need to double-check results. It’s exciting to see new techniques still being created to solve such an old problem, but we’ll stick with the Lucas-Lehmer test for now.
The Lucas-Lehmer Primality Test
Computers are helpful but the Lucas-Lehmer test was originally developed and done by hand. The method is so easy to write down it fits in 10 lines of Python code. Proving it works is not as straightforward, so we’ll understand a related piece of mathematics to get a feel for how the Lucas-Lehmer test works. Let’s focus on Fermat’s Little Theorem as a way to understand how the behavior of prime numbers can help us build a test to find them. We won’t prove anything here but I hope this provides a sense of how mathematicians can turn a property of a number into a way to detect it.
Fermat’s Little Theorem is a statement that shows one way in which prime numbers tie together exponents and modular arithmetic. It gives us an exponent that can be used to make any base equal to $1 \mod p$.
Fermat’s Little Theorem:
\[ a^{p-1} \equiv 1 \mod p \]
where $a$ is an integer and $p$ is a prime.
This feels very abstract, so let’s try the example from Wikipedia where $a=2$ and $p=7$.
\[ a^{p-1} \equiv 1 \mod p \implies a^{p-1} – 1 \equiv 0 \mod p \]
Keep in mind that $\equiv 0 \mod p$ is the same thing as saying a number is a multiple of $p$.
\[ 2^{7-1} – 1= 2^6 -1 = 64 -1= 63 \text{ is a multiple of 7, so } 63 \equiv 0 \mod 7 \]
The takeaway from this is to understand that raising any base to the power $p-1$ and having the result be equivalent to $1 \mod p$ is a property of every prime number, no matter how big. This means we know something about the prime numbers that have not yet been discovered. We use this knowledge to our advantage by changing how we use the equation. If we have a number that we hope is prime but aren’t sure, we can use Fermat’s Little Theorem to see if the candidate behaveslike a prime.
Let’s consider a candidate, $n$, and see how we can use Fermat’s Little Theorem to test if the candidate behaves like a prime. If we have a candidate, $n$, and check that $a^{n-1} \equiv 1 \mod n$ for many values of $a$, then $n$ is behaving like a prime number. We have to be careful here because the converse of Fermat’s Little Theorem here is not true. In our example, $n$ is behaving like a prime number but we don’t know for sure if $n$ is a prime number. The Carmichael Numbers live in the murky gap of behaving like something without being that thing, but we won’t venture there today.
We introduced Fermat’s Little Theorem to show how true statements about prime numbers can be used to detect them. We took a statement that is true for all primes and then used that relationship to test if an integer is behaving the same way prime numbers do. Unlike our approach with Fermat’s Little Theorem, the Lucas-Lehmer test is definitive and does not have the same “walks like a duck, quacks like a duck, but isn’t a duck” problem that the Carmichael Numbers create. Lucas-Lehmer’s proof closes that gap in two steps. First, Fermat’s Little Theorem is true for all primes, while the Lucas-Lehmer test only applies to primes of a very specific form. Second, the Lucas-Lehmer test uses iteration alongside exponentiation and modular arithmetic to create a sequence of numbers that end in zero if and only if the candidate is prime. This iteration is also why the test can be slow and why GIMPS runs it last.
With the background that the Lucas-Lehmer Test uses iteration to definitively prove a number prime, we can finally write it down. The entire test fits in 10 lines of Python. This code isn’t good enough to set new records, but it’ll prove, and beat, Lucas!
def LucasLehmer(p):
'''Returns True if the number 2^(p - 1) is prime, otherwise returns False'''
s = 4
M = (2**p) - 1
for i in range(p - 2):
s = (s**2 - 2) % M
if s == 0:
return True
else:
return False
p = 127
lucas_prime = (2 ** p) - 1
if LucasLehmer(p):
print(lucas_prime, 'is prime!')
else:
print(lucas_prime, 'is not prime.')
Running the code above gives us the output below.
170141183460469231731687303715884105727 is prime!
The number that took the record from Lucas, and from humans once and for all, was $M_{521} = 2^{521} – 1$. We can test that one too.
p = 521
M_p = (2 ** p) - 1
if LucasLehmer(p):
print(M_p, 'is prime!')
else:
print(M_p, 'is not prime.')
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 is prime!
We’ve beaten Lucas! To be fair, we did not really find a number bigger than Lucas’ – we looked one up and checked it. Next, we show how to discover $M_{521}$ for ourselves and then find even bigger primes. We use the same ideas GIMPS does when deciding which numbers to test next.
How do we know which numbers to test?
The Lucas-Lehmer test we’re using is powerful and easy to write down, but like many good things, these advantages come with a trade-off. The trade-off is our test only works in very specific settings. This test can only determine if the number $M_p = 2^p – 1$ is prime. It is not guaranteed that $M_p$ is prime, but $p$ must be prime for $M_p$ to even stand a chance. In short, we need a small prime number, like 2, 3, 127, or 521, to try to make a bigger one.
The proof that $p$ must be prime is challenging but we can try a few values to see how this idea could work.
$p=2$ is prime and $2^2 – 1 = 4 – 1 = 3$ is also prime.
$p=3$ is prime and $2^3 – 1 = 8 – 1 = 7$ is also prime.
$p=4$ is not prime and $2^4 – 1 = 16 – 1 = 15 = 3 \times 5$ is also not prime.
Every time I focus on abstractions for too long I’m always a bit shocked when examples like this work out. For completeness, we’ll see that if $p$ is prime $M_p$ doesn’t have to be prime, so one last example.
$p=11$ is prime and $2^{11} – 1 = 2048 – 1 = 2047 = 23 \times 89$ is not prime.
The point is that before we find a big prime we need a lot of small ones. There are several ways to find small primes, but an easy method that is fast enough for us is the Sieve of Eratosthenes. This wonderful animation from Wikipedia shows how it works, but you don’t need to understand the details to run the code.
By SKopp at German Wikipedia, used under the CC-BY-SA 3.0 licence.
def sieveOfEratosthenes(n):
'''Returns a list of all prime numbers up to n. Fairly quick for n up to 1,000,000.'''
candidates = {i:True for i in range(2, n)}
for i in candidates:
if candidates[i]:
for j in range(2*i, n, i):
candidates[j] = False
primes = [i for i in candidates if candidates[i]]
return primes
With this function we can generate lots of small primes. Let’s get all the primes up to 1,000 and beat Lucas without cheating.
N = 1000
primes = sieveOfEratosthenes(N)
print(f'Testing the {len(primes)} primes less than {N}. The largest prime less than {N} is {max(primes)}.')
mersenne_primes = []
for p in primes:
if LucasLehmer(p):
print(f'2^{p} - 1 = {2**p -1} is prime')
mersenne_primes.append(p)
print(f'\nFound {len(mersenne_primes)} Mersenne Primes - {mersenne_primes}')
print(f'The largest is 2^{max(mersenne_primes)} - 1 and it has {len(str(2**max(mersenne_primes)-1))} digits.')
The block above will generate a list of small prime numbers, each less than 1,000, and test each Mersenne Prime $M_p$ using the Lucas-Lehmer Primality Test. The code prints out each Mersenne Prime as it finds it and then tells us how big the longest one is. Its output is below.
Testing the 168 primes less than 1000. The largest prime less than 1000 is 997.
2^3 - 1 = 7 is prime
2^5 - 1 = 31 is prime
2^7 - 1 = 127 is prime
2^13 - 1 = 8191 is prime
2^17 - 1 = 131071 is prime
2^19 - 1 = 524287 is prime
2^31 - 1 = 2147483647 is prime
2^61 - 1 = 2305843009213693951 is prime
2^89 - 1 = 618970019642690137449562111 is prime
2^107 - 1 = 162259276829213363391578010288127 is prime
2^127 - 1 = 170141183460469231731687303715884105727 is prime
2^521 - 1 = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 is prime
2^607 - 1 = 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127 is prime
Found 13 Mersenne Primes - [3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607]
The largest is 2^607 - 1 and it has 183 digits.
The largest prime we found is $M_{607}$, which is even bigger than the 1952 recorder holder $M_{527}$. That means your computer has caught up with more than 2,000 years of mathematicians. Your computer just beat every human who has ever tried to find a large prime number by hand and you know something the famous Lucas did not. Try turning up the $N$ from $1,000$ to $2,000$ and see if your computer can find a prime so big it can’t fit in a tweet – that is, find a prime with more than 280 digits.
Going further
My laptop was able to check all numbers $2^p -1 $ for $p < 10,000$ and found the following $p$ generate Mersenne Primes.
That matches the OEIS list and Wikipedia page for Mersenne primes with $p < 10,000$. The biggest of these, $M_{9941} = 2^{9941} – 1$, held the record in 1963 and is mind-bogglingly big.
M_9941 has 2993 digits!
34608828249085121524296039576741331672262866890023854779048928344500622080983411446436437554415370753366448674763505018641470709332373970608376690404229265789647993709760358469552319045484910050304149809818540283507159683562232941968059762281334544739720849260904855192770626054911793590389060795981163838721432994278763633095377438194844866471124967685798888172212033000821469684464956146997194126921284336206463313859537577200462442029064681326087558257488470489384243989270236884978643063093004422939603370010546595386302009073043944482202559097406700597330570799507832963130938739885080198416258635194522913042562936679859587495721031173747796418895060701941717506001937152430032363631934265798516236047451209089864707430780362298307038193445486493756647991804258775574973833903315735082891029392359352758617185019942554834671861074548772439880729606244911940066680112823824095816458261761861746604034802056466823143718255492784779380991749580255263323326536457743894150848953969902818530057870876229329803338285735419228259022169602665532210834789602051686546011466737981306056247480055071718250333737502267307344178512950738594330684340802698228963986562732597175372087295649072830289749771358330867951508710859216743218522918811670637448496498549094430541277444079407989539857469452772132166580885754360477408842913327292948696897496141614919739845432835894324473601387609643750514699215032683744527071718684091832170948369396280061184593746143589068811190253101873595319156107319196071150598488070027088705842749605203063194191166922106176157609367241948160625989032127984748081075324382632093913796444665700601391278360323002267434295194325607280661260119378719405151497555187549252134264394645963853964913309697776533329401822158003182889278072368602128982710306618115118964131893657845400296860012420391376964670183983594954112484565597312460737798777092071706710824503707457220155015899591766244957768006802482976673920392995410164224776445671222149803657927708412925555542817045572430846389988129960519227313987291200902060882060733762075892299473666405897427035811786879875694315078654420055603469625309399653955932310466430039146465805452965014040019423897552675534768248624631951431493188170905972588780111850281190559073677771187432814088678674286302108275149258477101296451833651979717375170900505673645964696355331369819296000267389583289299126738345726980325998955997501176664201042888546085699446442834195232948787488410595750197438786353119204210855804692460582533832967771946911459901921324984968810021189968284941331573164056304725480868921823442538199590383852412786840833479611419970101792978355653650755329138298654246225346827207503606740745956958127383748717825918527473164970582095181312905519242710280573023145554793628499010509296055849712377978984921839997037415897674154830708629145484724536724572622450131479992681684310464449439022250504859250834761894788889552527898400988196200014868575640233136509145628127191354858275083907891469979019426224883789463551 is prime.
To catch up with the current record holder you would need a much more powerful computer and an improved version of our test. Currently, GIMPS takes about a month to test a single number and you can contribute directly to that project by running their code on your computer. You can learn more about the Greater Internet Mersenne Prime Search on their “How GIMPS Works” page.
We’ve had a bit of a break over the holidays, but mathematical news stops for no mince pie. From new prime numbers to mathematical doodling challenges, here’s a round-up of some of the facts/stories that we’ve seen while trying not to do any work.
We now know 50 Mersenne primes! The latest indivisible mammoth, $2^{77,232,917}-1$, was discovered by Great Internet Mersenne Prime Search user Jonathan Pace on the 26th of December 2017. As well as being the biggest Mersenne prime ever known, it’s also the biggest prime of any sort discovered to date.
GIMPS works by distributing the job of checking candidate numbers for primality to computers running the software around the world. It took over six days of computing to prove that this number is prime, which has since been verified on four other systems.
Pace, a 51-year old Electrical Engineer from Tennessee, has been running the GIMPS software to look for primes for over 14 years, and has been rewarded with a \$3,000 prize. When a prime with over 100 million digits is found, the discoverer will earn a \$50,000 prize. That probably won’t be for quite a while: this new prime has $23{,}249{,}425$ decimal digits, just under a million more than the previous biggest prime, discovered in 2016.
If you’re really interested, the entire decimal representation of the number can be found in a 10MB ZIP file hosted at mersenne.org. Spoiler: it begins with a 4.
The Great Internet Mersenne Prime Search, the premier distributed-computing prime finding initiative, has reported that $M_{32582657} = 2^{32,582,657}-1$, the 44th Mersenne prime to be discovered, is also the 44th Mersenne Prime in numerical order. It was found by Steven Boone and Curtis Cooper in 2006 (Cooper also discovered the current largest prime as reportedhere in February), but until now it was not known for certain that other, smaller primes had not been overlooked. GIMPS has now checked all the intervening Mersenne numbers for primality and having found nothing, $M_{32582657}$ is secure in its 44th-ness.
In a classic example of the intersection between maths and news, there’s been a new Mersenne prime discovered! Mersenne primes are numbers of the form $2^p – 1$, where $p$ is a prime number. They’re highly valued as a source of large prime numbers, since testing the primality of a (suspected) prime of this form is much easier than for general prime numbers.
