48th Mersenne prime found

http://www.mersenne.org/various/57885161.htm

by ColinWright • 13 years ago

327 109 13 years ago

mersenne.org

sikhnerd• 13 years ago

GIMPS "why" page is an interesting read as well: http://primes.utm.edu/notes/faq/why.html

crazcarl• 13 years ago

I was wondering what the significance of these findings were. I was disappointed that it is mostly "fame and fortune".

speeder3• 13 years ago

The absurd amount of time that takes just to verify the thing, shows how much we have yet to improve our computing power to be able to do more and more precise and groundbreaking science.

aartur• 13 years ago

But... numbers are an infinite, artificial construction, there always will be a number exceeding current computing powers by any wanted factor.

gejjaxxita5• 13 years ago

Mersenne primes may not be infinite ;)

speeder3• 13 years ago

This is why I mentioned calculating the proof, not finding a new one :)

TallGuyShort• 13 years ago

It sounds the primary motivation behind this project is exactly that. The intention is to push our ability to compute to it's limit.

antonb2011• 13 years ago

Hey, we should be thankful that primes have cardinality aleph_0, so we can have reasonable algos for exhaustive search at all! ;)

VMG• 13 years ago

There always will be a calculation that takes an absurd amount of time.

Simucal2• 13 years ago

I went to this university and took several of Professor Cooper's classes. He was a great guy and he seemed really passionate about his Mersenne project.

One thing that was annoying however was the prime finding software was put on every lab computer possible. It was suppose to pause when a user got on a machine and resume when they got off. This seemed to never be the case though because they would all run terribly slow and when you checked the process list the prime software would be pegging the CPU. After reporting the problem several times I simply added a line in my bash file to kill it when I logged on.

easytiger• 13 years ago

why on earth would they run it as you user?

Simucal2• 13 years ago

Several of us had root access to the few Linux boxes in the CS computer lab.

yock• 13 years ago

What OS was this? Processes like these (Folding, Seti, etc) should be "niced" on *nix-like OSes to have the lowest possible priority. Not sure what this looks like on Windows, but I imagine it's possible.

sp3323• 13 years ago

In windows, each process has one of 6 priority levels, and each thread has one of 7 priority levels. The combination is looked up in a table and yields one of 22 values between 1 and 31. http://msdn.microsoft.com/en-us/library/windows/desktop/ms68... You can manually change priority levels by right-clicking a process in the Task Manager. Not sure how to do it automatically or on a command line.

Edit: note the OS will "boost" priorities on certain processes or threads sometimes. http://msdn.microsoft.com/en-us/library/windows/desktop/ms68...

acdha2• 13 years ago

nice doesn't help with I/O pressure or memory contention, particularly if it used enough memory to contribute to swap activity. Even something like pressure on the system L2/L3 caches can be a big deal, particularly on older systems where those were less generous.

X-Istence• 13 years ago

That's sounds familiar. I went to a university where the one professor that was using Linux (and his knowledge was very little) was constantly tying up the Linux machines in our labs to run his prime number generation tool.

His research was into finding a faster/easier way to do prime number factorization in an attempt to speed up cryptography of any kind that uses it. Part of that was finding an easier/faster way to compute prime numbers in the first place. It was fascinating stuff ... but those machines were useless for anything but doing those calculations since it was using up all cores/HT's.

duck• 13 years ago

After reporting the problem several times I simply added a line in my bash file to kill it when I logged on.

It would have been discovered sooner if you hadn't done that. :)

DanBC• 13 years ago

David McOwen was a tech who installed distributed computing clients on the machines in his lab.

(http://www.securityfocus.com/news/300)

> A computer network administrator faces multiple felony charges and years in a Georgia prison for allegedly installing Distributed.net clients without permission. Prosecutors say its justice, others aren't so sure

> A college computer technician who offered his school's unused computer processing power for an encryption research project will be tried next month in Georgia for computer theft and trespassing charges that carry a potential total of 120 years in jail.

> The closely-watched case if one of the first in which state prosecutors have lodged felony charges for allegedly downloading third-party software without permission.

What a lot of people missed was the significantly raised electricity bills from having 500 PCs running this software all day.

And a gorgeously authentic 2001 page (http://freemcowen.com/)

EvanAnderson• 13 years ago

He ended up getting a year of probation (http://www.freemcowen.com/thelatest.htm).

Facing a huge prison sentence for "hacking"... sounds eerily familiar. >sigh<

ArbitraryLimits• 13 years ago

My university's physics department did the same thing with SETI@home. The SETI@home guys were smart enough to make their program run as a screen-saver that displayed Fourier Transforms so people thought it made the lab look more sciency and left it on.

stephengillie• 13 years ago

Another important note is that SETI@home actually did stop running when you were using the PC. If you left Task Manager up, you could see the difference on the CPU usage graph.

sanxiyn• 13 years ago

If we meet aliens, we should exchange Mersenne primes.

yesbabyyes2• 13 years ago

To them, that would be like someone wants to exchange integers with us.

- Fifteen THOUSAND!

- Uuuh...

gokhan• 13 years ago

You assume that they will be advanced enough to come to us. What if we find them in Europa or Titan?

gesman2• 13 years ago

...or claim that "my prime is bigger than yours" :)

NelsonMinar• 13 years ago

Good for GIMPS, 2⁵⁷⁸⁸⁵¹⁶¹ - 1 has a nice ring to it! GIMPS is one of the largest distributed computations in the world and have been tooling away finding primes since 1996. SETI@Home gets most of the credit for popularizing this kind of distributed computing, but GIMPS has been at it for even longer and has delivered consistent results.

falsestprophet• 13 years ago

To be fair, SETI@Home has delivered most consistent results.

yread• 13 years ago

you mean "nothing" ?

jpwagner• 13 years ago

this is not scalable :P

gesman2• 13 years ago

Finally! Now i can sleep well....

sp3323• 13 years ago

This part confuses me: "a 32-core server in 6 days" and "i7 CPU in 4.5 days" to do the same verification? Is the MLucas code really that much slower than GIMPS, or did the verification only use one core on the 32-core machine or what?

shocks• 13 years ago

The article does not mention how powerful these 32 server cores are.

masklinn• 13 years ago

Yes it seems very odd, especially as they also mention CUDALucas running in 3.7 and 7.7 days on two different NVidia GPUs (one a 560, the other one unnamed — maybe a Fermi board?)

sp3323• 13 years ago

I have the 560 Ti mentioned in the article. It's a mid-to-high grade card, better than most $200 cards IMHO but if you're willing to spend the cash, it's not at all difficult to find a card with more horsepower. Dropping a cool kilodollar will net you a GTX 690 which seems to be the right relative speed. http://www.hwcompare.com/12683/geforce-gtx-560-ti-vs-geforce...

Edit: since Dubslow's reply, here's the comparison for the GTX 580: http://www.hwcompare.com/9133/geforce-gtx-560-ti-vs-geforce-... It's also about $400.

mkl2• 13 years ago

Each of these verifications would have been using different code and algorithms, otherwise it's not really verification. So different speeds are entirely expected.

Dubslow3• 13 years ago

It's a myriad of answers. The Mlucas run used a larger FFT than was necessary, partly due to multithreading reasons. The Mlucas code also only uses SSE2 instructions, where the overclocked i7-2600K using GIMPS' Prime95 program is fully AVX capable. I would also expect that the i7 runs at a higher frequency, with a higher IPC, than the server. The "main" CUDALucas run took around 90 hours on a GTX 580. We didn't even hear about the 560 Ti run by Gilchrist, that was on the side.

Here are some links: http://www.mersenneforum.org/showpost.php?p=325878&postc... http://www.mersenneforum.org/showthread.php?p=325951#post325... http://www.mersenneforum.org/showpost.php?p=325995&postc... http://www.mersenneforum.org/showpost.php?p=326020&postc...

Dubslow3• 13 years ago

One last clarification: the reason to use Mlucas, and not Prime95 since it's so much faster, is for independent-code verification of the prime. (CUDALucas also counts in that regard, but the more independent triple and quadruple checks, the merrier!)

frozenport2• 13 years ago

Sounds like 2 AMD Opteron 6200 Interlagos chips as found on many clusters. Each has 16 cores, but they have only 8 floating point units and a smaller clock then their Intel counterparts.

For some codes each core gives 60% of an Intel core for many others it is 40%.

The Bulldozers and the Interlogos go down in my mind as the chip that destroyed the AMD. It late, was hard to use, and underperformed.

stevenleeg• 13 years ago

So what's the application of finding these sorts of primes? (I don't mean to sound like a dick or anything, I'm genuinely curious what this kind of knowledge can help us with).

jfrm• 13 years ago

http://primes.utm.edu/notes/faq/why.html

ville• 13 years ago

Large primes are used in cryptographic algorithms as well. http://math.stackexchange.com/a/43120

ColinWright• 13 years ago

Not Mersenne Primes, because they have a special structure that can create weaknesses.

vilgax• 13 years ago

It's used in field of cryptography. http://www.claymath.org/posters/primes/ http://primes.utm.edu/notes/faq/why.html

rorrr2• 13 years ago

Not Mersenne primes though. There are only a few of them, and it would be trivial to check if any of them are used as primes. The whole point of encryption schemes that use prime numbers is that the attacker doesn't know which primes are used.

jerf2• 13 years ago

Honestly, this is pretty much a "because we can" thing, other sibling replies to the contrary. It is cool and fun, and the resources dedicated to this are a pittance compared to, oh, say, the amount of computational resources applied to playing pretty 3D games.

ericHosick• 13 years ago

> the amount of computational resources applied to playing pretty 3D games.

The cool thing is that those pretty 3D games are one of the reasons why we have those nifty computational resources such as http://www.nvidia.com/object/tesla-servers.html.

cmsmith• 13 years ago

I think that the resources required deserve to be considered. If these computers are running 24 hours per day, and they require an extra 100 watts to look for primes (over their idle power consumption), then each computer is using the equivalent of 10 kg of coal per month.

In some cases, they're using renewable energy, and in some cases, they're offsetting heating costs. But the important thing is that the people installing the distributed computing software are not the people looking at the electricity bill. And that kind of breaks the whole economics of it.

mikecane• 13 years ago

Wolfram Alpha needs to update: http://www.wolframalpha.com/input/?i=what+is+the+largest+mer...

jrajav• 13 years ago

Well it's not up to date, but it's not wrong either. It says "Largest known ... as of July 2012"

undershirt2• 13 years ago

I first wondered they wouldn't just multiply all the prime numbers up to this new prime and then subtract one from it to get an even bigger prime number.

But then I realized that they're not searching for them in sequence. I guess it's a very sparse table of primes once you get up there in the magnitudes.

robterrell• 13 years ago

Or, you could test that theory with some smaller primes and realize it wouldn't work.

undershirt2• 13 years ago

oops.

ashleyblackmore• 13 years ago

If for whatever reason you want to download the number, there are a couple of links here:

http://www.isthe.com/chongo/tech/math/digit/m57885161/prime-...

rsiqueira• 13 years ago

In 2004, Liechtenstein issued a postage stamp with the 39th Mersenne prime number (2^13466917-1), this is the picture from a mathematical stamps collection: http://stamps.postbit.com/photos/math-stamps-collection/liec...

littledot5566• 13 years ago

When dealing with numbers of such magnitude, how are they stored in memory?

iand• 13 years ago

Even naively 2^257885161-1 can be represented with 257885161 bits, or 30MB.

kedean• 13 years ago

I'm not sure how GIMPS does it, but if you're interested in how it CAN be done you could look into the GMP library for C.

Dubslow3• 13 years ago

It's definitely just a standard lots-of-bits. Every bit of information is needed, lose one and the whole test will be wrong. For current wavefront exponents, like 2^60,000,000-1, save files are around 8 MB, or ~60M bits -- exactly what you'd expect.

Also Prime95 doesn't use GMP, its code is all hand-coded assembly, optimized specifically for the LL test and x86 architecture, written by one very dedicated George Woltman.

shaurz2• 13 years ago

They give the date to the nearest second but neglect to mention the year...

hfsktr• 13 years ago

Just imagine if we didn't have computers how many fewer primes would have been found.

Even with computers I started wondering how they even go about testing these. I know there are multiple algorithms etc for verification. I meant in the sense of how to keep everything in memory and doing computations on it (I assume that numbers these large aren't trivial to work with).

The history of mersenne primes was a an interesting read though. http://primes.utm.edu/mersenne/index.html

scythe• 13 years ago

The number's representation in binary can fit in RAM comfortably -- it's "only" 3 million bits or so. From there, the goal is to perform the Lucas-Lehmer test in as few operations as possible:

http://en.wikipedia.org/wiki/Lucas-Lehmer_test_for_Mersenne_...

pzxc• 13 years ago

In my freshman year of college, I discovered something neat about perfect numbers and Mersenne primes (verified by my math professor):

The first perfect number, 6, written in binary is 110 The second, 28, in binary is 11100 The third, 496, in binary is 1111100 The fourth, 8128, in binary is 1111111000000

See the pattern? Its a number of ones equal to the mersenne prime that generates the perfect number, followed by one less number of zeroes.

Just an interesting tidbit I discovered completely by accident in college that I always thought was cool. :)

Of course it derives directly from the fact that mersenne primes (and perfect numbers) are based on powers of two, but I still thought it was cool (probably because I discovered it accidentally and independently without trying to)

ctdonath4• 13 years ago

Awesome. I'll have to apply the binary notation approach to answering the question I just posted below.

jnotarstefano• 13 years ago

This is in fact the consequence of a fact first proven by Euler: every even perfect number is of the form (2^(p-1)) * (2^p - 1) where 2^p - 1 is a prime. That is, it's p ones shifted left by p-1 zeroes.

john_b• 13 years ago

In case anyone is curious, the explicit power of two formula for these perfect numbers can be found here: http://primes.utm.edu/mersenne/index.html#theorems

SagelyGuru• 13 years ago

Surely then the third should be: 111110000, not 1111100. Looks like you are two zeroes short of perfect ;)

ctdonath4• 13 years ago

I've long wondered:

Is 2^(2^(2^(2^(2^(...(2)...)-1)-1)-1)-1)-1 prime for all levels of recursion?

pndmnm• 13 years ago

Those are the Catalan-Mersenne numbers, and it is unknown whether c_5 is prime: http://oeis.org/A007013

ctdonath4• 13 years ago

May be. Each value in the series is, in binary, all 1s with the quantity of digits equal to the previous value in the series. Someone took a stab at this theory: http://www.mail-archive.com/mersenne@base.com/msg06260.html

czzarr• 13 years ago

tl;dr version:

The largest known prime number, 2^(57,885,161)-1, was discovered on January 25th 2013. It has 17,425,170 digits. The new prime number is a member of a special class of extremely rare prime numbers known as Mersenne primes... http://tldr.io/tldrs/51111f3dde23f15658000031/48th-known-mer...

pkamb• 13 years ago

> The discovery is eligible for a $3,000 GIMPS research discovery award.

Missed opportunity. Award should be $3,571.113

Yhippa• 13 years ago

Is 2^57,885,161-1 Numberwang?

ChrisClark• 13 years ago

Sorry, it was 3.

barbs• 13 years ago

Let's rotate the board!

xy22y• 13 years ago

If you care what the number actually is, and you have gnu bc, : echo '(2^57885161)-1' | bc > prime.txt

will yield a text file of 17,937,675 bytes, containing all the digits of the number, plus some overhead for newlines and continuation.

iso8859-1• 13 years ago

if you use a real Unix, you can use dc: »dc -e '2 57885161 ^ 1 - p'«

48th Mersenne prime found

Related Stories