How a Church Deacon Found the Biggest Prime Number Yet (It Wasn't as Hard as You Think)

[SummerMadness]

How a Church Deacon Found the Biggest Prime Number Yet (It Wasn't as Hard as You Think)

A huge math discovery in December was made in the unlikeliest of places: on a church computer in a Memphis suburb.

The background software running on the computer unearthed a rare kind of prime number called a Mersenne prime. It was the 50th and largest one to be found, containing over 23 million digits.

But for this behemoth to come to light, someone had to have installed free software used to search for Mersenne prime numbers, and that someone is Jon Pace, a deacon, FedEx finance manager and math aficionado who had spent 14 years hunting for such a number.

 

[Hammster]

That’s cool. For some reason, I just assume that the super computers these days can just crank them out.

 

[Sorn]

Yep, church computers in memphis are prime places to find such numbers!

 

[dgiharris]

That’s cool. For some reason, I just assume that the super computers these days can just crank them out.

not really.

Computers are stupid, they can only do what you tell them to do.
Mathematical formulas for prime numbers only work within certain limits and in the above case, 23 million digits is going to exceed the bounds of those formulas...

you'd quickly run into problems with trying to crank out bigger and bigger prime numbers. Remember, the definition of a prime number is a number that is only divisible by itself and 1.

What this means is that if you have a number 23 million digits long, then you've got to divide that number by every other single number up to 1/2 the value of the 23 million digit number.

So you'd need to perform calculations on the order of...
# of Calculations C = (1/2) x n

Lets say your computer operates at 3.5GHz which is 3.5 x 10^9 calculations per second

So, in order to find a prime number 23 million digits long it would take roughly ((1/2) x 10^23) / (3.5 x10^9) = 45,299 years

that's if we just did a straight calculation of the 23 million digit not to even include the iterative process of counting up to a number 23 million digits long. For instance, what about all the 22 million long digits and the 21 million long digits. What about the 23 million digit number plus 4, plus 5, plus 6. Once you throw in the iterative nature this quickly can blow up to several orders of magnitude.

Now, you can probably do some elimination to help, for instance you can automatically discount even numbers and numbers ending in 5 and then get rid of numbers that add up to something divisible by 3, but even with that, you are still only eliminated 60%-ish of the numbers.

even with all that, even with great processing power, you are still talking about a feat that would take tens of thousands of years via traditional iterative number crunching.

So it is nontrivial. In all likelihood, the program probably spit out giant random numbers, crunch them in an algorithm, and got lucky. Granted, we are talking about doing septillions of calculations per day for who knows how long before he "got lucky".

 

[Hammster]

not really.

Computers are stupid, they can only do what you tell them to do.
Mathematical formulas for prime numbers only work within certain limits and in the above case, 23 million digits is going to exceed the bounds of those formulas...

you'd quickly run into problems with trying to crank out bigger and bigger prime numbers. Remember, the definition of a prime number is a number that is only divisible by itself and 1.

What this means is that if you have a number 23 million digits long, then you've got to divide that number by every other single number up to 1/2 the value of the 23 million digit number.

So you'd need to perform calculations on the order of...
# of Calculations C = (1/2) x n

Lets say your computer operates at 3.5GHz which is 3.5 x 10^9 calculations per second

So, in order to find a prime number 23 million digits long it would take roughly ((1/2) x 10^23) / (3.5 x10^9) = 45,299 years

that's if we just did a straight calculation of the 23 million digit not to even include the iterative process of counting up to a number 23 million digits long. For instance, what about all the 22 million long digits and the 21 million long digits. What about the 23 million digit number plus 4, plus 5, plus 6. Once you throw in the iterative nature this quickly can blow up to several orders of magnitude.

Now, you can probably do some elimination to help, for instance you can automatically discount even numbers and numbers ending in 5 and then get rid of numbers that add up to something divisible by 3, but even with that, you are still only eliminated 60% of the numbers.

even with all that, even with great processing power, you are still talking about a feat that would take tens of thousands of years via traditional iterative number crunching.

So it is nontrivial. In all likelihood, the program probably spit out giant random numbers, crunch them in an algorithm, and got lucky. Granted, we are talking about doing septillions of calculations per day for who knows how long before he "got lucky".

Thanks for that.

 

[dgiharris]

Thanks for that.

no problem,

but in the interest of full disclosure, what I wrote would give a mathematician fits because I'm leaving a lot of stuff out and I'm slightly wrong on a few points. But conceptually, what I said is 90% right...

 

[iluvatar5150]

From the article:

It Wasn’t as Hard as You Think

No, he just had to leave his computer running for 14 years and hope to get lucky. He'd have been much, much better off mining bitcoin.

 

[Tinker Grey]

What this means is that if you have a number 23 million digits long, then you've got to divide that number by every other single number up to 1/2 the value of the 23 million digit number.

So you'd need to perform calculations on the order of...
# of Calculations C = (1/2) x n

Actually, you need only divide by numbers up to the square root of the number being tested.

 

[dgiharris]

Actually, you need only divide by numbers up to the square root of the number being tested.

duh

thanks