27 ms·

M(57885161) verified as 48th Mersenne Prime

163 points by mattashii 5y ago

jacquesm 5y ago
The staying power of this project is very impressive, and the fact that even with the long interval between finds (years) that doesn't seem to detract from dedicating CPU power to the project. Carbon footprint anyone? ;)
- kevingadd 5y ago
  If only we could use stuff like this or protein folding as the "work" in proof of work...
  - koheripbal 5y ago
    Primecoin
  - tomerv 5y ago
    That could really be a great thing! The problem is that Mersenne primes are "sparse", i.e. there aren't many of them. Finding one could be like minting a new block, but it would be so rare that it won't be practical. For crypto, you would need something with many solutions, but then it's probably not so useful to find yet another solution...
    - the8472 5y ago
      maybe proof that a large block of numbers doesn't contain mersenne primes?
  - dnautics 5y ago
    you also generally speaking need something that is much easier to verify than it is to generate. I'm not saying it's impossible, but I don't think that "verifying" a protein folding in the "cryptocurrency" sense is a meaningful operation in the "useful" way you're hoping it to be.
- np_tedious 5y ago
  Can you explain finding Mersenne primes so CPU intensive? Mₙ = 2ⁿ − 1 gives an easy to generate candidate set and testing primality of a single number isn't that expensive. 57885161th candidate being the 48th hit is getting pretty sparse I guess, but it isn't that crazy. What am I missing? Seems the compute would be rather small compared to much of the "big data" / NN training done every day
  - Someone 5y ago
    Because they are so big. 10³ > 1,000, so in decimal, 2^57,885,161 - 1 has over 3 × 5,788,516 digits, so over 17 million. You do not check whether that is a prime by trial division (https://en.wikipedia.org/wiki/Trial_division https://en.wikipedia.org/wiki/Trial_division). If you could do a division every nanosecond and had a billion devices, that would still take way, way more time than till the heat death of the universe to do. We have better tests (https://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests https://en.wikipedia.org/wiki/Primality_test#Fast_determinis...), but the best generic one still is Õ((log n)⁶). Here, log(n) is about 58 million, so that log(n)⁶ has over 46 digits. We can do better, as we don’t need a generic test. for Mersenne numbers, there’s https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test.
  - jacquesm 5y ago
    Because of the numers 'in between', once you start testing that many numbers in such an enormous range it eats up CPU power. There is some very beautiful math trickery which uses an FFT to help determine if a number is prime or not, and even though that's a massive optimization the number of remaining cycles required is still enormous. See here for more background: https://www.mersenne.org/various/math.php https://www.mersenne.org/various/math.php
    - np_tedious 5y ago
      Are Mersennes any more or less likely to be excluded by a probabilistic primality test than other numbers might be?
llampx 5y ago
Could someone tell me as a layperson, how finding these numbers is helping humanity?
- eloff 5y ago
  This is hardly the most frivolous thing humanity does. It's ok if it never has any practical applications.
  - ramraj07 5y ago
    On a different eon that might be true but nowadays compute power - electricity - global warming. Given that, “frivolous” work that just burns energy could be potentially postponed until we go fully renewable in our energy stack.
    - medo-bear 5y ago
      lol ... bless you
    - f-jin 5y ago
      You're in for a tough one once you find out that reality TV and video-games exist.
      - mrpopo 5y ago
        Or calculating SHA-256 hashes (ok this one already gets bashed out appropriately). Or running AC until you need a jacket.
    - eesmith 5y ago
      There seem to be many frivolous uses of power to complain about when you get to this level of power use. GIMPS' ~1PetaFLOPS[1] uses no more than a megawatt [2]. That's about 10 Gigawatt-hours (GWh) over a year [3]. The average US house uses about 10 MWh in a year [4] so GIMPS = the electrical power use of ~1,000 households. Portland reduced their power consumption by 20 GWh by switching their street lights to LEDs[5]. The electrical consumption for Superbowl parties is an estimated 75 GWh [6]. (I think Superbowl parties are far more frivolous.) [1] - https://www.mersenne.org/primenet/ https://www.mersenne.org/primenet/ [2] from 2012, "HP plans to deliver a full peak petaflop with just a single megawatt" - https://www.hpcwire.com/2012/09/05/hp_intel_score_petaflop_supercomputer_at_doe_lab/ https://www.hpcwire.com/2012/09/05/hp_intel_score_petaflop_s... [3] 365.25days * 24hours/day * 1MW / 1000 = 8.8 GWh [4] "In 2020, the average annual electricity consumption for a U.S. residential utility customer was 10,715 kilowatthours (kWh)" https://www.eia.gov/tools/faqs/faq.php?id=97&t=3 https://www.eia.gov/tools/faqs/faq.php?id=97&t=3 [5] https://www.portlandoregon.gov/transportation/article/678781 https://www.portlandoregon.gov/transportation/article/678781 [6] https://www.americasgenerators.com/blog/post/2017/02/15/What-it-Takes-to-Power-Up-the-Super-Bowl.aspx https://www.americasgenerators.com/blog/post/2017/02/15/What...
hutrdvnj 5y ago
I think computer benchmarks should compute something useful, like mersenne prime verification. Million of benchmarks are run every day mostly on newer device with decent computing power. This amounts to a large amount of currently unused cycles. Maybe it would be possible to create a block-chain technology in which their participants calculate something scientifically meaningful.
- VMG 5y ago
  This is a common misconception. In order for a Proof-of-Work algorithm to be useful, there must be an opportunity cost (penalty) to mining on the wrong chain. If the mining algorithm pays off anyway it cannot be used.
  - rytill 5y ago
    What if it’s a public good that we generally believe everyone benefits from, like mathematics research? No individual would pay for it, but it’s still more valuable than random noise.
    - rsj_hn 5y ago
      Patents allow mathematical research to be excludable and thus not a public good. Now one can argue that mathematical patents provide more costs than benefits, which is a line of debate I am certainly open to. End that, and math research would be a public good. But in the system we have now, a huge amount of mathematical research has generated a significant amount of money for very many people, from the RSA algorithm to Penrose patenting his tilings (and getting money from toilet paper makers that used his aperiodic tilings to make their TP more fluffy [1]) What I think you mean to say is that the market consistently undervalues mathematical research. Unfortunately it's not so easy to actually demonstrate, because given the huge amount of math research produced, only a very small amount of that ends up being useful in the future and often the original discoverer is long dead. This is similar to the situation with other arts and sciences. A small number of people drive the field forward and the vast majority of scientific publications are basically filler. Certainly the world would be better with more effective funding mechanisms that we have on offer, which is basically a game of capture-the-grant. [1]https://apnews.com/article/59354892d1875c277c91afd3fb5ca516 https://apnews.com/article/59354892d1875c277c91afd3fb5ca516
mseidl 5y ago
Crap, now I'm going to have to change the combination on my luggage.
- devoutsalsa 5y ago
  Imagine having 2^57885161 - 1 rollers on your luggage & having the lock bypassed by the low tech TSA key :)
- analog31 5y ago
  If its a binary lock, the combination was easy to guess.
- deleted 5y ago
  [deleted]
ramshanker 5y ago
I imagine, one day when we finally break the factoring problem, we are going to have a bunch of these prime. This is one of the things I prat to see in my remaining lifetime.
- quantdev 5y ago
  It's very possible we never break the factoring problem. Since we have no properly unified theory of physics (e.g., one that models the observer in QFT), there are outstanding unknowns with quantum computing that may make it so that Shor's algorithm is not practically useful.
Archelaos 5y ago
Aprox. how much energy did this test consume?
mike_d 5y ago
This is a verification, the next likely Mersenne prime M(74207281) has already been discovered. Verification just involves eliminating all lower possibilities. https://www.mersenne.org/primes/ https://www.mersenne.org/primes/
- karmakaze 5y ago
  Thanks for this context. rank p digits discovered 48 257,885,161-1 17,425,170 2013 Jan 25 49* 274,207,281-1 22,338,618 2016 Jan 07 50* 277,232,917-1 23,249,425 2017 Dec 26 51* 282,589,933-1 24,862,048 2018 Dec 07 So we've already found three larger ones but have still yet to be verified as the 49th, 50th, 51st consecutive ones. Verification seem of more interest to those following closely and discovery of another one being bigger.
Ansil849 5y ago
I think one of the biggest mysteries (in my mind anyway), is how Mersenne found his original list of primes. Yes, some were shown to be incorrect and some he missed...but him finding the amount that he did still seems amazing to me, and I don't believe this has ever been explained. It seems to me like he had a private method for calculating primes (that was imperfect, sure, but also astounding for being developed in the 17th century). To me it feels like when this is brought up, modern day mathematicians are too quick to dismiss him based on the incorrect numbers/the missed primes, and ignore the many correct ones and the question of _how_ he managed to find them. That's what I would like to know, is his method.
- pvg 5y ago
  Yes, some were shown to be incorrect and some he missed It's a small sample but it's worse than you make it sound, I think. He came up with four new numbers, given what was known at the time. Half were wrong and he missed three. Whatever method he'd come up with, it was pretty badly mistaken. It's curious, historically, but almost certainly mathematically uninteresting.
  - Ansil849 5y ago
    > Whatever method he'd come up with, it was pretty badly mistaken. It's curious, historically, but almost certainly mathematically uninteresting. He did not just stumble onto two correct primes in the 17th century by chance. He had used a seemingly now-lost process that was semi-fruitful. This should be worthy of investigation, not dismissed as "mathematically uninteresting". Mersenne somehow figured out M(127)...in the early 1600s, and no one to this day seems to know how. How is this not mathematically interesting?
    - pvg 5y ago
      He did not just stumble onto two correct primes in the 17th century by chance. M31 you can verify by hand, which really leaves us with one out of four. It's entirely possible he got one right by chance. It probably wasn't strictly by chance, very likely convinced himself of some pattern that doesn't really hold. There are plenty of neat-looking lines in, say, an Ulam spiral but those don't generate primes either.
xyzelement 5y ago
I ask thos question with genuine curiosity- can someone help me understand why this is important? I have the same question about a lot of esoteric fields on Math - do we study them just because of curiosity and seeing how far we can follow a pattern? Or is there actual value to for example knowing what Mersenne primes are, etc? I guess my question is - is this applied in any way? EDIT: I see from responses my comment created the impression that I conflate "purely intellectual" and "not valuable." That was not my intention, simply asking whether this has applications or not.
- Ansil849 5y ago
  The only things "important" are having basic food to eat and a place to sleep. Everything else in life is "curiosity". It is incredibly annoying when the question of importance is brought up, typically when things like pure mathematics, or art, or humanities are being discussed. Why does no one ask, "can someone explain what's important about working for a FAANG company, what do they produce that's of any importance*.
  - kibwen 5y ago
    > Why does no one ask, "can someone explain what's important about working for a FAANG company, what do they produce that's of any importance. No, no, we ask that all the time. :P
- villasv 5y ago
  > can someone help me understand why this is important Because it was hard > is this applied in any way Not sure, but this is a vacuous way to define what is important
elahieh 5y ago
What always fascinated me about this sequence was the huge (multiplicative) gap between the exponents: 2^127 - 1 and 2^521 - 1. If that property continued after 2^20,996,011 - 1 the next one would be around 2^86,133,241-1 which is bigger than the (provisional) 51st Mersenne prime, so we'd be stuck at "40th verified Mersenne prime found in 2003". Which really makes you wonder about the density of these primes in exponent terms ...

163 points by mattashii 5y ago

The staying power of this project is very impressive, and the fact that even with the long interval between finds (years) that doesn't seem to detract from dedicating CPU power to the project. Carbon footprint anyone? ;)

kevingadd 5y ago
If only we could use stuff like this or protein folding as the "work" in proof of work...
- koheripbal 5y ago
  Primecoin
- tomerv 5y ago
  That could really be a great thing! The problem is that Mersenne primes are "sparse", i.e. there aren't many of them. Finding one could be like minting a new block, but it would be so rare that it won't be practical. For crypto, you would need something with many solutions, but then it's probably not so useful to find yet another solution...
  - the8472 5y ago
    maybe proof that a large block of numbers doesn't contain mersenne primes?
- dnautics 5y ago
  you also generally speaking need something that is much easier to verify than it is to generate. I'm not saying it's impossible, but I don't think that "verifying" a protein folding in the "cryptocurrency" sense is a meaningful operation in the "useful" way you're hoping it to be.
np_tedious 5y ago
Can you explain finding Mersenne primes so CPU intensive? Mₙ = 2ⁿ − 1 gives an easy to generate candidate set and testing primality of a single number isn't that expensive. 57885161th candidate being the 48th hit is getting pretty sparse I guess, but it isn't that crazy. What am I missing? Seems the compute would be rather small compared to much of the "big data" / NN training done every day
- Someone 5y ago
  Because they are so big. 10³ > 1,000, so in decimal, 2^57,885,161 - 1 has over 3 × 5,788,516 digits, so over 17 million. You do not check whether that is a prime by trial division (https://en.wikipedia.org/wiki/Trial_division https://en.wikipedia.org/wiki/Trial_division). If you could do a division every nanosecond and had a billion devices, that would still take way, way more time than till the heat death of the universe to do. We have better tests (https://en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests https://en.wikipedia.org/wiki/Primality_test#Fast_determinis...), but the best generic one still is Õ((log n)⁶). Here, log(n) is about 58 million, so that log(n)⁶ has over 46 digits. We can do better, as we don’t need a generic test. for Mersenne numbers, there’s https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test.
- jacquesm 5y ago
  Because of the numers 'in between', once you start testing that many numbers in such an enormous range it eats up CPU power. There is some very beautiful math trickery which uses an FFT to help determine if a number is prime or not, and even though that's a massive optimization the number of remaining cycles required is still enormous. See here for more background: https://www.mersenne.org/various/math.php https://www.mersenne.org/various/math.php
  - np_tedious 5y ago
    Are Mersennes any more or less likely to be excluded by a probabilistic primality test than other numbers might be?

llampx 5y ago

Could someone tell me as a layperson, how finding these numbers is helping humanity?

eloff 5y ago
This is hardly the most frivolous thing humanity does. It's ok if it never has any practical applications.
- ramraj07 5y ago
  On a different eon that might be true but nowadays compute power - electricity - global warming. Given that, “frivolous” work that just burns energy could be potentially postponed until we go fully renewable in our energy stack.
  - medo-bear 5y ago
    lol ... bless you
  - f-jin 5y ago
    You're in for a tough one once you find out that reality TV and video-games exist.
    - mrpopo 5y ago
      Or calculating SHA-256 hashes (ok this one already gets bashed out appropriately). Or running AC until you need a jacket.
  - eesmith 5y ago
    There seem to be many frivolous uses of power to complain about when you get to this level of power use. GIMPS' ~1PetaFLOPS[1] uses no more than a megawatt [2]. That's about 10 Gigawatt-hours (GWh) over a year [3]. The average US house uses about 10 MWh in a year [4] so GIMPS = the electrical power use of ~1,000 households. Portland reduced their power consumption by 20 GWh by switching their street lights to LEDs[5]. The electrical consumption for Superbowl parties is an estimated 75 GWh [6]. (I think Superbowl parties are far more frivolous.) [1] - https://www.mersenne.org/primenet/ https://www.mersenne.org/primenet/ [2] from 2012, "HP plans to deliver a full peak petaflop with just a single megawatt" - https://www.hpcwire.com/2012/09/05/hp_intel_score_petaflop_supercomputer_at_doe_lab/ https://www.hpcwire.com/2012/09/05/hp_intel_score_petaflop_s... [3] 365.25days * 24hours/day * 1MW / 1000 = 8.8 GWh [4] "In 2020, the average annual electricity consumption for a U.S. residential utility customer was 10,715 kilowatthours (kWh)" https://www.eia.gov/tools/faqs/faq.php?id=97&t=3 https://www.eia.gov/tools/faqs/faq.php?id=97&t=3 [5] https://www.portlandoregon.gov/transportation/article/678781 https://www.portlandoregon.gov/transportation/article/678781 [6] https://www.americasgenerators.com/blog/post/2017/02/15/What-it-Takes-to-Power-Up-the-Super-Bowl.aspx https://www.americasgenerators.com/blog/post/2017/02/15/What...

hutrdvnj 5y ago

I think computer benchmarks should compute something useful, like mersenne prime verification. Million of benchmarks are run every day mostly on newer device with decent computing power. This amounts to a large amount of currently unused cycles. Maybe it would be possible to create a block-chain technology in which their participants calculate something scientifically meaningful.

VMG 5y ago
This is a common misconception. In order for a Proof-of-Work algorithm to be useful, there must be an opportunity cost (penalty) to mining on the wrong chain. If the mining algorithm pays off anyway it cannot be used.
- rytill 5y ago
  What if it’s a public good that we generally believe everyone benefits from, like mathematics research? No individual would pay for it, but it’s still more valuable than random noise.
  - rsj_hn 5y ago
    Patents allow mathematical research to be excludable and thus not a public good. Now one can argue that mathematical patents provide more costs than benefits, which is a line of debate I am certainly open to. End that, and math research would be a public good. But in the system we have now, a huge amount of mathematical research has generated a significant amount of money for very many people, from the RSA algorithm to Penrose patenting his tilings (and getting money from toilet paper makers that used his aperiodic tilings to make their TP more fluffy [1]) What I think you mean to say is that the market consistently undervalues mathematical research. Unfortunately it's not so easy to actually demonstrate, because given the huge amount of math research produced, only a very small amount of that ends up being useful in the future and often the original discoverer is long dead. This is similar to the situation with other arts and sciences. A small number of people drive the field forward and the vast majority of scientific publications are basically filler. Certainly the world would be better with more effective funding mechanisms that we have on offer, which is basically a game of capture-the-grant. [1]https://apnews.com/article/59354892d1875c277c91afd3fb5ca516 https://apnews.com/article/59354892d1875c277c91afd3fb5ca516

mseidl 5y ago

Crap, now I'm going to have to change the combination on my luggage.

devoutsalsa 5y ago
Imagine having 2^57885161 - 1 rollers on your luggage & having the lock bypassed by the low tech TSA key :)
analog31 5y ago
If its a binary lock, the combination was easy to guess.
deleted 5y ago
[deleted]

ramshanker 5y ago

I imagine, one day when we finally break the factoring problem, we are going to have a bunch of these prime. This is one of the things I prat to see in my remaining lifetime.

quantdev 5y ago
It's very possible we never break the factoring problem. Since we have no properly unified theory of physics (e.g., one that models the observer in QFT), there are outstanding unknowns with quantum computing that may make it so that Shor's algorithm is not practically useful.

Archelaos 5y ago

Aprox. how much energy did this test consume?

mike_d 5y ago

This is a verification, the next likely Mersenne prime M(74207281) has already been discovered. Verification just involves eliminating all lower possibilities. https://www.mersenne.org/primes/ https://www.mersenne.org/primes/

karmakaze 5y ago
Thanks for this context. rank p digits discovered 48 257,885,161-1 17,425,170 2013 Jan 25 49* 274,207,281-1 22,338,618 2016 Jan 07 50* 277,232,917-1 23,249,425 2017 Dec 26 51* 282,589,933-1 24,862,048 2018 Dec 07 So we've already found three larger ones but have still yet to be verified as the 49th, 50th, 51st consecutive ones. Verification seem of more interest to those following closely and discovery of another one being bigger.

Ansil849 5y ago

I think one of the biggest mysteries (in my mind anyway), is how Mersenne found his original list of primes. Yes, some were shown to be incorrect and some he missed...but him finding the amount that he did still seems amazing to me, and I don't believe this has ever been explained. It seems to me like he had a private method for calculating primes (that was imperfect, sure, but also astounding for being developed in the 17th century). To me it feels like when this is brought up, modern day mathematicians are too quick to dismiss him based on the incorrect numbers/the missed primes, and ignore the many correct ones and the question of _how_ he managed to find them. That's what I would like to know, is his method.

pvg 5y ago
Yes, some were shown to be incorrect and some he missed It's a small sample but it's worse than you make it sound, I think. He came up with four new numbers, given what was known at the time. Half were wrong and he missed three. Whatever method he'd come up with, it was pretty badly mistaken. It's curious, historically, but almost certainly mathematically uninteresting.
- Ansil849 5y ago
  > Whatever method he'd come up with, it was pretty badly mistaken. It's curious, historically, but almost certainly mathematically uninteresting. He did not just stumble onto two correct primes in the 17th century by chance. He had used a seemingly now-lost process that was semi-fruitful. This should be worthy of investigation, not dismissed as "mathematically uninteresting". Mersenne somehow figured out M(127)...in the early 1600s, and no one to this day seems to know how. How is this not mathematically interesting?
  - pvg 5y ago
    He did not just stumble onto two correct primes in the 17th century by chance. M31 you can verify by hand, which really leaves us with one out of four. It's entirely possible he got one right by chance. It probably wasn't strictly by chance, very likely convinced himself of some pattern that doesn't really hold. There are plenty of neat-looking lines in, say, an Ulam spiral but those don't generate primes either.

xyzelement 5y ago

I ask thos question with genuine curiosity- can someone help me understand why this is important? I have the same question about a lot of esoteric fields on Math - do we study them just because of curiosity and seeing how far we can follow a pattern? Or is there actual value to for example knowing what Mersenne primes are, etc? I guess my question is - is this applied in any way? EDIT: I see from responses my comment created the impression that I conflate "purely intellectual" and "not valuable." That was not my intention, simply asking whether this has applications or not.

Ansil849 5y ago
The only things "important" are having basic food to eat and a place to sleep. Everything else in life is "curiosity". It is incredibly annoying when the question of importance is brought up, typically when things like pure mathematics, or art, or humanities are being discussed. Why does no one ask, "can someone explain what's important about working for a FAANG company, what do they produce that's of any importance*.
- kibwen 5y ago
  > Why does no one ask, "can someone explain what's important about working for a FAANG company, what do they produce that's of any importance. No, no, we ask that all the time. :P
villasv 5y ago
> can someone help me understand why this is important Because it was hard > is this applied in any way Not sure, but this is a vacuous way to define what is important

elahieh 5y ago

What always fascinated me about this sequence was the huge (multiplicative) gap between the exponents: 2^127 - 1 and 2^521 - 1. If that property continued after 2^20,996,011 - 1 the next one would be around 2^86,133,241-1 which is bigger than the (provisional) 51st Mersenne prime, so we'd be stuck at "40th verified Mersenne prime found in 2003". Which really makes you wonder about the density of these primes in exponent terms ...