# Prime Prize

April 12, 2007 5:57 PM Subscribe

In September 2006 the largest known prime number, a 9.8 million digit number, was discovered. If you find one over ten million digits you can win US$100,000 (of which you get to keep $50,000). No maths is required - just download the software and you're away. Warning: it takes about a month to run one primality check so some patience is required. Look out though Cooper and Boone look like they might beat you to it.

Is there a practical reason for looking for very large primes or is this strictly for curiosity's sake?

posted by empath at 6:19 PM on April 12, 2007

posted by empath at 6:19 PM on April 12, 2007

*Is there a practical reason for looking for very large primes or is this strictly for curiosity's sake?*

Mostly for curiosity's sake. Number theory is kinda of like a unicorn in mathematics, as there are a lot of mathematicians who pursue studies in number theory even though there aren't (yet) many real applications of it. The most notable application is the importance they play in public key cryptography.

Disclaimer: I'm just a CS student and don't have a strong mathematical background so I could be wrong on this.

posted by patr1ck at 6:26 PM on April 12, 2007

Wouldn't making a 10 million digit prime be exceptionally simple? Find two numbers whose product is a 10 million digit number, then take the factorial of that product, add one, and you have a prime number.

posted by tylermoody at 6:51 PM on April 12, 2007

posted by tylermoody at 6:51 PM on April 12, 2007

*Find two numbers whose product is a 10 million digit number, then take the factorial of that product, add one, and you have a prime number.*

A factorial plus one isn't necessarily prime. (eg. 4!+1 = 25 = 5x5, 5!+1 = 121 = 11x11).

I suspect you mean something other than 'factorial'. Anyway, no, it's not easy.

posted by painquale at 7:06 PM on April 12, 2007

I got a couple I just thought of.

posted by Falconetti at 7:10 PM on April 12, 2007

posted by Falconetti at 7:10 PM on April 12, 2007

i've been a fan of www.mersenne.org for quite awhile. they also have links to lots of other neat stuff, including (at one point, don't know if it's still there) one where you can help nasa catalogue martian photographs.

posted by bruce at 7:33 PM on April 12, 2007

posted by bruce at 7:33 PM on April 12, 2007

Fuckin' taxes are brutal.

posted by Gnostic Novelist at 7:43 PM on April 12, 2007

posted by Gnostic Novelist at 7:43 PM on April 12, 2007

What I think you

2*3*5*7*11*13*17*...*nthprime + 1 is guaranteed prime, since it can't possibly be divisible by any of the same prime factors as the number prior.

However, I'm guessing there are practical limitations to this trick that make it non-trivial to generate large new primes that way. For one thing, this method does not, itself, produce consecutive primes, so to come up with fuel for it you'd have to generate sequential primes by some more completist (and hence probably much slower) method. Maybe there's a bottleneck there?

And I might be forgetting something basic and important. Not a number theorist.

posted by cortex at 7:44 PM on April 12, 2007

*can*do is multiply together consecutive prime factors, from 2 on up through*n*, and add 1 to*that*. That right there will be a prime number.2*3*5*7*11*13*17*...*nthprime + 1 is guaranteed prime, since it can't possibly be divisible by any of the same prime factors as the number prior.

However, I'm guessing there are practical limitations to this trick that make it non-trivial to generate large new primes that way. For one thing, this method does not, itself, produce consecutive primes, so to come up with fuel for it you'd have to generate sequential primes by some more completist (and hence probably much slower) method. Maybe there's a bottleneck there?

And I might be forgetting something basic and important. Not a number theorist.

posted by cortex at 7:44 PM on April 12, 2007

Between this and that fractal that's at least as big as my apartment, I'm convinced: Math is crazy, and therefore my high school GPA is excusable.

posted by gordie at 8:23 PM on April 12, 2007

posted by gordie at 8:23 PM on April 12, 2007

Cortex, those are Euclid numbers, and they break down pretty early:

E6 = 13# + 1 = 13*11*7*5*3*2+1 = 30031 = 59 x 509

posted by aeschenkarnos at 8:23 PM on April 12, 2007 [1 favorite]

E6 = 13# + 1 = 13*11*7*5*3*2+1 = 30031 = 59 x 509

posted by aeschenkarnos at 8:23 PM on April 12, 2007 [1 favorite]

(And now, looking at it and knowing there's a problem, I can see the problem. Take

posted by cortex at 8:30 PM on April 12, 2007

*that*, Euclid!)posted by cortex at 8:30 PM on April 12, 2007

Euclidian Math holds that Euclidian numbers are always euclidian. 7 will always be my favorite prime number

posted by longsleeves at 8:39 PM on April 12, 2007

posted by longsleeves at 8:39 PM on April 12, 2007

what practical reason could there possibly be?

posted by longsleeves at 8:42 PM on April 12, 2007

posted by longsleeves at 8:42 PM on April 12, 2007

My house number theorist says:

Yes, public key cryptography is the main current practical use for the prime search. But the old saw around math departments is that every discovery in number theory will be come practically useful 50 years from the time it's discovered. (as physics, engineering, or computer science advance)

Perfect numbers are an interesting related topic, one of the standard building blocks of analytic number theory. Every Mersenne prime gives you a new perfect number. So, we discover

posted by LobsterMitten at 9:16 PM on April 12, 2007

Yes, public key cryptography is the main current practical use for the prime search. But the old saw around math departments is that every discovery in number theory will be come practically useful 50 years from the time it's discovered. (as physics, engineering, or computer science advance)

Perfect numbers are an interesting related topic, one of the standard building blocks of analytic number theory. Every Mersenne prime gives you a new perfect number. So, we discover

*two*things of number theoretic interest by finding new Mersenne primes.posted by LobsterMitten at 9:16 PM on April 12, 2007

The main practical purpose for fast factorization is its application to NP-complete problems. Putting aside mathematical jargon, an NP-complete problem is a problem that can only be solved by trying every possible potential solution. The classic example is the travelling salesman, who wishes to visit

So, if it took us a second to examine a path, and we had to visit 5 cities, it would take us 120 s to brute-force it, or 800 s to do it the "smart" way. Doesn't seem very smart? Try 100 cities. 100! ~= 9.33 x 10

We could, and we do, save time by partitioning the problem. If we employed 100 people, and each was told to start always at a certain city, we could cut the time down to only ~ 1.27 x 10

Clearly, the travelling salesman problem has been solved in practice, and is in fact solved all the time by every one of us every day. The key is the limits of acceptability: if the post office is a block from the bank, and four blocks from the supermarket, and the video store is five miles out of town, then we're going to visit the bank, the supermarket, and the post office in some order, without going to the video store between two local stops. Close enough is good enough.

However, for primality, and for applications such as cryptography that depend on absolute exactitude, close enough isn't good enough. A number is prime or it isn't. You may very quickly come to the conclusion that it isn't--half of all numbers are non-prime due to divisibility by 2, 1/3 by 3, etc, trailing off into a logarithmic tail of diminished probability of being prime--but you cannot, at present, come to the conclusion that a number

That's why a fast factoring algorithm is the holiest of Holy Grails of number theory. Come up with a way to do this, or unassailably prove that you

posted by aeschenkarnos at 12:08 AM on April 13, 2007

*n*cities exactly once each, in the order that will minimize the length of his journey. If we take a brute-force approach, examining every possible path, there are*n*-factorial paths. We can be smarter about it, but the smartest we've gotten (according to the Wikipedia article) will still force us to examine*n*^{2}x 2^{n}paths.So, if it took us a second to examine a path, and we had to visit 5 cities, it would take us 120 s to brute-force it, or 800 s to do it the "smart" way. Doesn't seem very smart? Try 100 cities. 100! ~= 9.33 x 10

^{157}s, but 100^{2}x 2^{100}~= 1.27 x 10^{34}s, which is, obviously, an enormous saving of time.We could, and we do, save time by partitioning the problem. If we employed 100 people, and each was told to start always at a certain city, we could cut the time down to only ~ 1.27 x 10

^{32}s. If we used a computer that could perform 10^{9}calculations per second, it will only take us ~ 1.27 x 10^{25}s to work through the problem. We could buy a million such computers, and cut our time down to ~ 1.27 x 10^{19}s. Unfortunately, the universe is only about 10^{16}seconds old, so we're going to have to come up with some other method.Clearly, the travelling salesman problem has been solved in practice, and is in fact solved all the time by every one of us every day. The key is the limits of acceptability: if the post office is a block from the bank, and four blocks from the supermarket, and the video store is five miles out of town, then we're going to visit the bank, the supermarket, and the post office in some order, without going to the video store between two local stops. Close enough is good enough.

However, for primality, and for applications such as cryptography that depend on absolute exactitude, close enough isn't good enough. A number is prime or it isn't. You may very quickly come to the conclusion that it isn't--half of all numbers are non-prime due to divisibility by 2, 1/3 by 3, etc, trailing off into a logarithmic tail of diminished probability of being prime--but you cannot, at present, come to the conclusion that a number

*is*prime without having stepped through all possible integer factors up to and including its square root (rounded down). Make the number one binary digit longer, and you double the time it takes to do this.That's why a fast factoring algorithm is the holiest of Holy Grails of number theory. Come up with a way to do this, or unassailably prove that you

*can't*, and we enter a new order of comprehension of mathematics and all things that derive from mathematics, physics being the preeminent example. My own*suspicion*--for which I have no rational basis, I freely admit it as a superstitious/romantic belief--is that a fast factoring algorithm would equate to a perpetual motion machine, which breaks conservation of mass/energy, which is why it can't be done. I'd like to be wrong about that.posted by aeschenkarnos at 12:08 AM on April 13, 2007

*Is there a practical reason for looking for very large primes or is this strictly for curiosity's sake?*

Thought for thought's sake of course requires no practical reason -- it would be worth doing even if there were no financial reward. It's also relatively cheap research with no rooms full of suffering wired monkeys.

But there are at least two very practical reasons for encouraging mathematicians to find ways to find integers that can't be divided by any other integers (except themselves and 1, of course):

1. Seemingly pointless mathematical discoveries can become tools for solving real-world problems. As mentioned above, prime numbers are an important factor (heh) in modern cryptography. One mathematician comes up with one silly proof, another mathematician comes up with another silly proof, and a third mathematician finds a way to use those proofs to prove something else. Proof builds on proof and eventually, we always hope, we get something like a fast and simple way to calculate optimal routes for all the truck and rail and air traffic in the world, which saves all of us trillions of dollars while reducing the pollution caused by trucks and trains and planes.

2. It keeps mathematicians busy and off the streets. Think of the danger of having these otherwise unemployable folk figuring out scams (other than getting grants). What if they

*became*the traveling salesman problem -- twisted calculating geniuses going door to door. You wouldn't even know you'd been scammed unless they told you, and even then only they'd be able to prove the crime and understand the proof.

posted by pracowity at 12:50 AM on April 13, 2007 [1 favorite]

Can the species please stop its idiotic addiction to prime numbers? Like, yesterday. The Riemann hypothesis needs to go the way of the dodo. And group theory, too.

posted by oonh at 3:30 AM on April 13, 2007

posted by oonh at 3:30 AM on April 13, 2007

Yeah, quit with the prime number thing and go back to something useful, like finding more digits to Pi.

posted by Mr.Encyclopedia at 4:08 AM on April 13, 2007 [1 favorite]

posted by Mr.Encyclopedia at 4:08 AM on April 13, 2007 [1 favorite]

*Yeah, quit with the prime number thing and go back to something useful, like finding more digits to Pi.*

Every prime number exists somewhere in the decimal expansion of pi. By finding large prime numbers, you are automatically finding more digits of pi (of course, you have no idea where in pi they occur).

posted by Bort at 9:43 AM on April 13, 2007

*Every prime number exists somewhere in the decimal expansion of pi.*

Is that proven?

posted by cortex at 10:23 AM on April 13, 2007

*Is that proven?*

It depends upon whether the decimal expansion of pi is random or not. I thought it was shown to be, but cannot find a link stating that. IF it is random, then it contains every finite number, a subset of which is the primes.

I'll see if I can find something conclusive tonight after work.

posted by Bort at 10:49 AM on April 13, 2007

Nope, I was wrong. From wiki, it is still an open question as to whether pi is random or not. So my statement has not been proven.

posted by Bort at 11:41 AM on April 13, 2007

posted by Bort at 11:41 AM on April 13, 2007

pie are round; cornbread are square.

posted by longsleeves at 9:21 PM on April 14, 2007

posted by longsleeves at 9:21 PM on April 14, 2007

sorry

posted by longsleeves at 9:21 PM on April 14, 2007

posted by longsleeves at 9:21 PM on April 14, 2007

the set of random numbers and the set of infinite numbers both don't exist.

posted by longsleeves at 9:24 PM on April 14, 2007

posted by longsleeves at 9:24 PM on April 14, 2007

All I meant is: a set will have boundaries

posted by longsleeves at 8:10 PM on April 15, 2007

posted by longsleeves at 8:10 PM on April 15, 2007

« Older baa | Bourne on the Bayeux. Newer »

This thread has been archived and is closed to new comments

posted by Mr. President Dr. Steve Elvis America at 6:08 PM on April 12, 2007