2^74207281-1 is Prime | Hacker News Reader

2^74207281-1 is Prime

mersenne.org

304 pointsramshanker124 comments

Glad I actually read the article because I never would have known this:

"The official discovery date is the day a human took note of the result. This is in keeping with tradition as M4253 is considered never to have been the largest known prime number because Hurwitz in 1961 read his computer printout backwards and saw M4423 was prime seconds before seeing that M4253 was also prime."

Also "Dr. Cooper's computer reported the prime in GIMPS on September 17, 2015 but it remained unnoticed until routine maintenance data-mined it." I'd have thought that BIG FLASHING LIGHTS would go off if a prime were reported. Maybe with CELEBRATORY KLAXONS.

E-mail notification failed according to Professor Curtis Cooper in interview for Matt Parker's "Standup Math" youtube channel:

http://m.youtube.com/watch?v=q5ozBnrd5Zc

I think they should send to printer :-)

Teletype printer, no less. Perhaps even a old paper stock ticker.

Or better yet, have a "morning scrum" :-) looking at the result every morning.

    if result is true:
       write_to_a_file(result)

So if a mathematical fact is known by one person, "it is known."

That's how existence proofs work.

I have seen aliens.

And I'm sure you'll have no more trouble proving the existence of aliens than the fine mathematician who was the first to discover a fact.

So, let's see your proof.

As long as you are talking about mathematical aliens, as in mathematical objects that are so different from every other know mathematical object currently recognized in the corpus of Math.

If you further claim that this objects are, like, sentient... I guess this would be too Pythagorean for my tastes. ;)

And if it's known by more than one person, it's "trivial" :)

Tim Gowers' informal definition of "trivial" is: "when a proof springs to mind"

Big numbers are fun. Here's some stupid stuff I thought of while reading about this.

The number is 2^74,207,281 - 1. Naively stored like a normal integer in memory, that's roughly 75 MB of RAM just to store the number. Compare that to your 64-bit time_t and imagine how long a duration of time could be represented by such a large number. Stored on 3.5" floppy disks for some reason, that's roughly 50 disks just to store the number.

Edit: Duh, bits, not bytes. I leave my mistake here for posterity.

Not unless you gzip it. Since the number is just the binary 1 repeated a bunch of times, it should gzip pretty well.

Repeated exactly 74,207,281 times, to be precise...

No, the number 5 is prime, yet in binary it is 101. The new prime number could have many zeroes interspersed with ones, so you don't know how many 1 digits it has.

EDIT: I have realized my mistake in the representation of 2's complement. However, I will leave this here for posterity.

But 5 is not 2^n-1

5 is a prime number true, but not a Mersenne prime number. The Mersenne prime number 31 has 5 as its exponent n [1].

[1] http://mathworld.wolfram.com/MersennePrime.html

It's a Mersenne Prime, so it is 1 less than some power of 2. This results in all of its non-leading digits in binary being 1s.

Turns out run-length encoding it is more or less what you get if you store it as 2^74,207,281 - 1. I imagine this probably is how they store it actually; note that 2^n == 1<<n so you can just store the exponent and complement (74 207 281, 1) and then do normal two's complement math.

If you're talking about storing it in computer memory during calculation, then no, it's written out. The fast MOD operation you list isn't used, it's an FFT using a weight factor that automatically does the mod operation while squaring a number. You start with S[0] = 4, S[i+1] = Si^2 - 2 MOD N. If S[N-2] = 0 then the number is prime.

So it's 74,207,279 squares using FFT, each likely more than 75 MiB since there will likely be lots of leading zeros (we're probably close to the maximum number of digits using double precision, round off errors dominate unless you start using really small bases and even greater-length FFTs).

That's not counting the two or three compositeness tests that GIMPS uses before starting the Lucas-Lehmer test to prove primality.

For several years I've been working on a program to test for primality of the Generalized Fermat numbers, using NTT instead of FFT. NTT is exact (integer math), and the GFNs likely are more "dense" with primes than the Mersenne Numbers. And they also have a faster form to test, although the primality test has a 50% chance of false negative, so you have to run it a few times to be sure a number isn't prime. That's where Mersenne Numbers are easier to test.

So I tried it and it's 72135 bytes using tar czf (created by `fs.writeFileSync('/tmp/file',new Buffer(74207281).fill("1"),'utf8')`)

Not that it's the most efficient representation at all, 74207281 fits in 4 bytes.

M49 (for the 49th mersenne prime) fits in 2 bytes! Or even better just 49! 6 bits! Assuming your decompression algorithm is optimized for mersenne primes. :)

It can fit in a single bit if your algorithm is optimized for "primes that are equal to M49" :)

You could optimize the single bit away by assuming that there would be a bit.

http://www.dangermouse.net/esoteric/lenpeg.html

Great, I've just discovered the 50th mersenne prime, M50. Decompression takes a lot of time.

This thread is officially dumb. One guy miscalculates 75 Mbit as ~75 MiB, another guy fills ~70 MiB file with ASCII "1"s.

dumb, but fun

Strange but very useful things could emerge from just mucking about and poking around...

Hehe, I didn't mean to sound negative! Agree with the other poster that it's quite fun.

Oh, and I also forgot to mention that the guy used `tar` for compressing one file. I'll see myself out.

I'm glad I started this stupid thread, and this is my favorite comment in it.

It's the sort of thing that's so repetitive you end up gzipping the gzip, because the "repeat N times" code doesn't support going so high.

gzipped it's a 9043 byte file when the source is the number expressed exactly as bits. gzipping that 9043 byte file yields a 129 byte file, which gzip can't compress any further. Base64 of the file:

  H4sICBPHnlYCA2EuYmluegDt0LENQQEUQNHnK7xINF8rLIAVbKH88VU0ZlATK4gt1DQ6vURMoBID
  iN4CknOa29/BNrN72U+LZj2eL1fxPDU6EXE+3CbvUTEMAAAAAAAAAODfPfq9/DZfx6petw2B32Z5
  XZT31mYXH9vDv0RTIwAA

I see some redundancy there. The letter "A" appears many times in a row.

Also it could be compressed even further. All you need is a computer program that prints "1", 74 million times.

It's already been concisely expressed as 2^74,207,281 - 1, so you don't need a computer program that prints "1" 74 million times.

You just need a computer language that can interpret bignum math equations.

That would take ages to compute. Printing one is faster. And might produce the smallest file size if it's done in assembly.

but the metric was the most concise way to store the data

Neato! Verified with:

  echo "H4sICBPHnlYCA2EuYmluegDt0LENQQEUQNHnK7xINF8rLIAVbKH88VU0ZlATK4gt1DQ6vURMoBIDiN4CknOa29/BNrN72U+LZj2eL1fxPDU6EXE+3CbvUTEMAAAAAAAAAODfPfq9/DZfx6petw2B32Z5XZT31mYXH9vDv0RTIwAA" | base64 --decode | gzip -d | gzip -d | xxd

Looks like you just communicated it in 16 bytes though.

That's 75 megabits, not megabytes.

75 Megabits; 9.5 MB/7 3.5" floppies/5-10 selfies.

You're right! Thanks! I told you it was stupid :P

How many t-shirts?

Someplace used to print Mersenne primes as posters. IIRC they were using a font around 2 points. Probably given up now...

The person died, and the art with him :( http://www.mersenneforum.org/showthread.php?t=19100

I remember those. They either came with a loupe, or mentioned explicitly to the buyer that you needed one to see individual numbers. Always wanted to get one. It looked like an all grey poster if you didn't know what it was.

75 MB compresess neatly to under 12 bytes, which I say because the string "2^74207281-1" is totally unambiguous (Wolfram Alpha will evaluate it for you no questions asked, no guesswork, though obviously it only approximates the output). So the Kolmogorov complexity of the 75 MB is 96 bits or less.

I think there's a related mathematical paradox about the largest number that can be represented by an English phrase of fewer than 93 characters.

Or you create a new compression scheme just for Mersenne prime numbers where store the exponent. You'll be able to compress the entire number into just 32 bits for several decades at least!

Since the exponent is prime you should be able to compress it further than that, by simply noting n is the kth prime number. Supposedly as n goes to infinity the probability that n is prime drops to zero, so that should compress handily.

Decompressing it, on the other hand, would be pretty slow however. Are primality tests O(n) or O(nlogn)? That puts decompression up to O(n^2) without a pre computed lookup table.

https://en.wikipedia.org/wiki/Prime_number_theorem#Approxima...

So with the kth prime ~= k log k, the ratio of primes is 1 / log k. Yes that drops to zero, but very slowly.

You can use the upper bound of the kth prime to build a sufficiently large sieve, which can be done O(n).

If you don't care about computation time, then why stop there?

You can encode the Mth Mersenne with the integer M.

But then I have to keep patching the code every time a new one comes out. Too hard!

You don't. You can write a program that converts between m and M_m. It just takes a long time to convert.

It is far too many bits to be used for time representation. 512 bits is all that needed to store every planck time (10^-44 seconds) since the big bang until the heat death of the universe (10^100 years).

Sure, that's fine if all you want is to measure the time from the big bang until the last matter in the universe has evaporated into photon soup. But what if you want the time until those photons are evenly distributed? An article I read a while back estimated that duration as 10^10^78 years, which is absolutely mindboggling and remains the largest number I have ever seen with a real-world physical application.

(It may never happen, though; according to Wikipedia, random quantum fluctuations may be sufficient to produce another Big Bang in a mere 10^10^56 years.)

That makes sense for durations, but a time_t is actually a timestamp. A proper time can have the same units as a duration, but is only useful in conjunction with information about the trajectory of the clock measuring the time. If space is continuous, the amount of information to specify the trajectory is limited only by the capabilities of the measurement apparatus. Of course, for all we know at this point spacetime is quantized; so we should probably hold off on standardizing the time format to end all time formats.

If you were abducted by aliens, and had memorized that number, you could possibly trade it for wealth in their society. If they hadn't discovered it yet!

If an alien were abducted by humans, and it memorized a much larger prime number, what would we give in exchange for that piece of information?

Apparently a $3,000 GIMPS research discovery award. What's the practical utility of knowledge of a prime, especially considering that upon announcement it's immediately disseminated?

The point of searching for these primes is to motivate research in finding primes so there isn't much practical utility.

It's a very large prime number which has a very convenient representation, which makes it useful. You could use it in a Mersenne Twister RNG, for instance.

Some Hacker News points, for sure!

The amount of CPU cycles burned to get this result surely translates into some dollar value.

Everybody contributes to the MP for free but that doesn't mean there isn't any value involved. It's a donation of sorts.

Interestingly, if the alien's memorized number was significantly larger (e.x. tens of billions of digits) we would not be able to verify it. It took three and a half days to verify the correctness of M74207281 on two 18-core Xeon servers, and with speed increases in computing slowing down it may be a very long time before we are able to verify a number that large.

So, nothing. The alien could say "Oh yeah, we have 2^34240923842043983204982-1" and they could be absolutely correct but there's nothing we could do to know.

Or, if their number was big but not that big, it might be able to be verified in, say, a year, in which case it might win the EFF's prize and could possibly get some other sort of prize money. So, $150k + some undefined amount.

2^34240923842043983204982-1 is divisible by 3.

How'd you do that?

Write out the number in decimal, add the digits together: if the result is larger than a single digit, repeat. When you have a single digit, if it is 3, 6 or 9, the number is divisible by 3.

The proof is left as an exercise for the student.

How did you write out the number? It's 10307545155701210591839 digits long.

I'll get back to you once I find a piece a paper large enough to write down the 10 sextillion decimal digits.

That's the divisibility check for 3, yes, but I am pretty sure fdej didn't write that number out in decimal. The proof doesn't work with exponents. You'd have to represent the number in base 10 for digit summing to work.

To check, 2^6-1=63 is divisible by three (it might work), but 2^9-1 has a sum of 12 and a value of 511, which is not divisible by three (it's 170 * 3 = 510 + 1).

The sequence 2^n mod 3 goes 2, 1, 2, 1, 2...

That's how you solve all problems of this form. For any a and b, a^n mod b eventually becomes periodic as n grows. It's easy to prove because there's only a finite number of possible remainders mod b. As an exercise, calculate 3^1000000 mod 7.

a ^ (n - 1) ~= 1 mod n if n is prime, Fermat's Little Theorem.

3 is prime. 34240923842043983204982 is divisible by 3 - 1 = 2.

ab mod n = [a mod n * b mod n] mod n

So, we can automatically infer that 2 ^ 34240923842043983204982 ~= 1 mod 3.

After subtracting 1, it will be divisible by 3.

Alternatively, you could notice that 2 ^ 2 ~= 1 mod 3, which implies 2 ^ 4 ~= 1, 2 ^ 6 ~= 1, so 2 ^ all even powers will be congruent to 1 modulo 3.

So 2 ^ x - 1 will always be divisible by 3 for even x.

http://www.amazon.com/The-Peripheral-William-Gibson/dp/03991...

correction: some rational alien society

I'm curious to understand the significance of finding the largest known prime numbers. It seems that some people get pretty excited but I'm not sure if it's just purely academic or there's some useful applications I'm unaware of. Can anyone enlighten me?

I am curious too. I wonder if this has anything to do with the public key encryption relying on prime numbers.

EFF has a bounty for large prime numbers: https://www.eff.org/awards/coop

"The EFF awards are about cooperation," said John Gilmore, EFF co-founder and project leader for the awards. "Prime numbers are important in mathematics and encryption, but the real message is that many other problems can be solved by similar methods."

Finding these prime numbers will be no simple task, given today's computational power. It has taken mathematicians years to uncover and confirm new largest known primes. However, the computer industry produces millions of new computers each year, which sit idle much of the time, running screen savers or waiting for the user to do something. EFF is encouraging people to pool their computing power over the Internet, to work together to share this massive resource. In the process, EFF hopes to inspire experts to apply collaborative computing to large problems, and thereby foster new technologies and opportunities for everyone.

> However, the computer industry produces millions of new computers each year, which sit idle much of the time, running screen savers or waiting for the user to do something.

Considering how much more electricity a running computer uses versus an idle one and how much faster consumer CPUs degrade under load this definitely seems like a huge waste of resources for something that has little, if any, utility.

I used to run prime95 on all of my machines, back when power management (especially on desktops) was virtually nonexistent. Obviously, with the power management features we have now, an idle CPU (especially outside of a hosting environment) is not considered wasteful.

I assume it's somewhat academic in nature, but I could speculate it may have some cryptography applications where Prime's are used heavily.

One of the key features of pure mathematics is that we come up with results just to have sitting around, on the off chance they ever become useful. And often they do, much later on. It’s a gift to the future.

Prime numbers are tricky things. They are one of the most fundamental parts of our numerical systems, but they're difficult to predict.

You would kind of expect that something so elementary should be easily predictable, or follow a pattern. But while we've found some similarities (like the mersenne primes) there's still a kind of nagging feeling that there should be a more basic way to enumerate prime numbers than guess and check.

We've learned some simple things about them, such as the existence of Mersenne primes, or ideas on the probability of any given number being prime being inversely proportional to its logarithm.

But I think the biggest thing is that it's a puzzle. But a puzzle that bothers us because it seems like it should be easy to solve, but it's not.

Finding larger prime numbers tells us more about them. It lets us see other parts of patterns. Patterns that might lead to some insight on how to predict if a number is a prime, or how to factor large numbers. This might have an impact on cryptography for instance.

But finding this number doesn't solve a problem, it adds to a body of knowledge. It fills in a bit of the puzzle. In the end the hope is that we learn something about the puzzle, or at the least, learn why we can never learn something about the puzzle.

It's similar to Barry Bonds hitting the most home runs. It serves the world nothing but lots of exercise for Barry, but it's an achievement that everyone can feel proud about. In addition, the GIMPS project has contributed to an efficient FFT and to distributed computing research.

This sort of thing is comparable to sending humans to the Moon. In and of itself, there's not much of a point to it; but the technology you develop to get there has a tendency to become useful in other, perhaps more useful, areas.

In the case of the Mersenne prime hunt, you need the fastest integer multiplication algorithms (and concrete implementations) you can. Fast integer multiplication is a big part of several useful number-theoretic algorithms. An interesting (to me) application is, for example, to check whether a number is only divisible by small primes. This is an integral part of the most efficient integer factorization algorithms known, and one way to do it is with a product tree followed by a remainder tree [1]. This would be unacceptably slow without quasilinear-time multiplication algorithms.

[1] https://cr.yp.to/lineartime/multapps-20080515.pdf

I like this Moon analogy you've made. I'm sure it's a broad stroke but still serves as a simple and effective answer to the question. Thanks.

In 1940, Hardy used the theory of numbers as an example of a profoundly and permanently useless discipline in A Mathematicians Apology[1]. The fact that number theory is the basis for modern cryptography gives the lie to this sentiment.

The fact is that we don't know whether the search for Mersenne primes, or any other mathematical endeavour, will reveal anything useful, but given the depth of interconnection between different branches of mathematics and the usefulness of some of those branches, it doesn't seem plausible that we won't find useful things.

Although Hardy turned out to be wrong about number theory and its applications, his arguments for the intrinsic value of the study of mathematics in the absence of any real utility stand as well.

And of course, as another commenter has pointed out, making computers do things like this is a great way to develop phenomenally fast and useful algorithms.

Finally, the project found a bug in Intel CPUs[2], which is kind of neat...

[1] https://www.math.ualberta.ca/mss/misc/A%20Mathematician's%20... [2] http://www.extremetech.com/computing/220953-skylake-bug-caus...

It's purely academic.

I had to find out what a Mersenne number was again (vaguely remember but forgot) and I was shocked to find this problem in mathematics:

"It is not known whether or not there is an odd perfect number, but if there is one it is big! This is probably the oldest unsolved problem in all of mathematics." [1]

[1]: http://primes.utm.edu/mersenne/index.html

> The primality proof took 31 days of non-stop computing on a PC with an Intel I7-4790 CPU.

How does this work? You just try to divide by every possible number and ensure the result isn't an integer?

You only need to divide by prime numbers up to ceil(sqrt(your_number)).

They don't know all prime numbers up to this number, but they can easily exclude many numbers (for example even).

That would still take an eternity.

They use special form primes (the big primes are all n+1 or n-1 forms, with n being easy to factor).

If a Mersenne Number is prime, then the exponent must also be prime (74,207,281 is also prime). That cuts down on a lot of processing time.

Also, all factors of a Mersenne Number, if it's composite, are of the form 2nk + 1, where the Mersenne number is written 2^n - 1. That also helps factor it. I generated a huge list of prime number indices and did some tests on them a couple of years ago. 25% of the Mersenne numbers have 2*n + 1 as a factor. That's even less computation time to find a large prime.

Or any composite number. If it's divisible by a composite number, it will also be divisible by the smaller primes.

This are the simplest insights for optimizing primality test. A nice exercise to implement if you like algorithms. More info: https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes

I believe they actually have very optimized algorithms to test for primality [0], which not necessarily involve diving by every possible number.

There are simple tests and there are more complex ones, that use probabilities and other workarounds to avoid having to divide by every possible number.

[0] https://en.wikipedia.org/wiki/Primality_test

They use the Lucas–Lehmer primality test [0], along with trial factoring candidate numbers up to a given bit depth to sift out some composites from the prime candidates quicker than a full LL test.

[0] https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality...

Nice. Only the 49th Mersenne yet discovered. This also gives us a new perfect number, 2^(74207281-1)(2^74207281-1).

Meanwhile, somewhere in Wisconsin, the number 274-207-2811 is being mercilessly prank-called my mathematicians.

22,338,618 digits long, 1 More step towards EFF award for first 100 Million digit prime number.

I wonder how much it would cost to generate that using EC2 spot instances.

Amazon would like for you to try.

Probably way more than other hosting providers. :^)

Well. If you pick a number at random and test it, and the first one you happen to pick is it, then surely not much.

One needs to check starting with n = 332192831, the 17896982-th prime. Here 2^n-1 has > 100 Million digits.

Wow, many years since I've contributed to the project with my little cluster, nice to see them still going strong.

Incidentally, the project source code contains one of the fastest Fourier transform implementations that I'm aware of.

Do you happen to know how it compares to kissfft or fftw?

Good question, no, no idea but of those two fftw would appear to have the edge so if you're going to compare do it with that one. I do know the fftw guys benchmarked an older version of it but I can't find the results (there used to be a bunch of graphs showing the relative performance of all those ffts listed).

It should be fairly easy to figure this out though, the benchmark code is public and if fft sizes you are interested in are known you could make a very precise comparison.

One warning about the mersenne fft code, it is not the most readable one on account of all the optimizations, but if all you're interested in is a drop-in library then it might suit your needs, especially if the size fft you're after is one that has already been optimized to the hilt by the mersenne project people. If you find you need to customize it then you're probably better off with a more universal implementation, even at the expense of some cycles.

I have a stupid question that will reveal how I know nothing about cryptography. I understand that large primes are somehow important for some types of cryptography. How are there not just databases of large primes that make breaking the types of cryptography that rely on large primes trivial?

There are _a lot_ of large primes. If you randomly choose a 1024 bit prime, it's _extremely unlikely_ anybody seen or used that prime before you.

There are too many. Not just more than could fit in every database on Earth. More than could fit on every database if every star in the sky had an Earth, each with as many databases as there are on Earth.

This is nothing specific to cryptography or prime numbers. Fun fact: if you shuffle a deck of cards correctly, it's almost certain that no one in history has ever had a deck in the exact same order. https://www.math.hmc.edu/funfacts/ffiles/10002.4-6.shtml

I understand that there's a huge number of primes, but surely the primes being used to generate keys or whatever process they're involved in are "known" primes, right? It's not as if when I try to encrypt something my machine is going to search for a new prime number that hopefully won't get guessed.

Long prime numbers are used for RSA keys. You only generate RSA keys when creating a new identity (webserver certificate, client certificate, SSH key, etc). Then, you do search for "a new prime number that hopefully won't get guessed". It can take from a few seconds to several minutes, depending on the hardware and the desired key length.

The usual approach is to take a random odd number of desired length and then have a probabilistic primality test (much faster than what would be needed for a formal proof). Several attacks rely on bad entropy or bad pseudo random number generators (PRNG) to guess what prime was selected.

Are there any double Marsenne primes that we know of? Where 2^(2^n - 1) - 1 is prime as well?

2^3-1 = 7 => prime 2^7-1 = 127 => prime 2^127 - 2 is also prime

is there anything special you can do with mersenne primes? if there's no pattern to them, can't it just be seen as dumb luck?

They represent the largest known primes, as the special case 2^n-1 allows us to verify their primeness using a method much more efficient than checking all potential factors.

So to answer your question, if there's ever a need for ridiculously large numbers that are known to be prime this is how we'll fill it.

Short of that need, it's still fun as a mathematical world record!

I love this. So M49 is now the largest known prime, but what does it take to find the next prime number? Or any larger prime?

A buttload of electricity

I downloaded and checked the zip file. Last digit is a 6. Downloaded it multiple times to test. Can anyone else replicate this?

If I have read it correctly, the last digit is a 1. This is the end of the file I downloaded:

...010073391086436351

Edit: Confirmed by https://www.youtube.com/watch?v=q5ozBnrd5Zc

I'll try a different tool to decompress the file maybe. a 6 would have made no sense. What was your uncompressed file size? I ended up with 44.7MB

  % tail -1 M74207281/M74207281.txt
  010073391086436351
  % du M74207281/M74207281.txt
  44504	M74207281/M74207281.txt
  % md5 -q M74207281/M74207281.txt
  53294de131970c2cee8da6fe9a3135b3

Here are the last "few" digits:

7302483892184777905493456249144515504366

7354352576469730088553216748038660370944

9872555291212307480179276559709617648630

5356033886997788467889060830923906229428

0028777084668153501142762292122183690404

5477963931367013401448014940470411696633

4745646885160717774014762912462113646879

4258014451073931002129271816293359314942

3901821387921767116495628719049868701007

3391086436351

Reply on news.ycombinator.com