Saturday, January 23, 2016

Largest Prime

A computer at the University of Central Missouri -- and the mathematician there, Curtis Cooper, who has 800 machines running looking for primes -- has found the largest prime number known to-date:  274,207,281 − 1. It's called a Merseene prime, because it's of the form 2M-1. It's about 22 million digits long, abou t5 million more than the previous record, and written out it comes to this ridiculous thing that begins with

three hundred septenmilliamilliaquadringensexquadraginmilliaduocenquattuortillion...  

Numberphile shows how it was done, and says anyone can download the search program and run it. (You can even win money.)

By the way, appx 2,300 years ago Euclid proved, very simply and elegantly, that there are infinitely many prime numbers. There are other proofs as well.

I wanted to understand how to calculate how many digits this new prime has.

It's pretty clear that the number of digits d(N) for any number N is (in base 10)

d(N) = INT[log10(N)] + 1

where INT(x) returns the integer portion of the number x -- everything to the left of its decimal point. For a Merseene prime this becomes

d(M) = INT[log10(2M-1)] + 1

However, we can't readily compute 2M -- it's too large, but after thinking awhile here's what I came up with:

No power of 2 has a last digit of 0 (easy to prove via induction), so the last digit of 2M does not end in zero. 2M is even, so its last digit is either 2, 4, 6, or 8. So 2M -1 has a last digit of 1, 3, 5, or 7, but not 9 because 2M never has a last digit of 0. (It also can't end in 3 or 5, because it'd be evenly divisible by the same integer; unless it was 3, which is the first Mersenne prime.) So the last digit of 2M-1 can only be 1 or 7.

Hence, the integer part of log10 of 2M-1 will be the same as the integer part of log10 of 2M. So

d(M) = INT[log10(2M)] + 1 = INT[Mlog10(2)] + 1

which is easily calculated -- in this case it comes to 22,338,618.

Wolfram has a list of Mersene primes, with strings of their first several digits and last several digits. Sure enough, they all end in 1 or 7.

Interesting:  If 2M-1 is prime, then M is prime. Slate says the 11 largest known primes are all Merseene primes (and the article has other interesting facts about primes). Notably, it has been conjectured ther are an infinite number of Merseene primes, but not proven.

Prime numbers are interesting and weird. Statements about them are often easy to make, but very difficult to prove. They leak into other important areas of mathematics, like Riemann's Hypothesis. It almost seems like there is some hidden part of the geography of all mathematics, relatively simple and straightforward and, like a lost city, just waiting to discovered behind a towering mountain pass. Some 22-year old genius in the year 2273 will finally bridge the gap by going around the pass, not over it, opening up a whole new world.


Doug Cotton said...
This comment has been removed by a blog administrator.
David Appell said...

Doug Cotton: Your comment was completely off-topic. So I removed it.

Oale said...

And what is currently the smallest REAL prime? By this I mean the smallest number used in applied physics?

David Appell said...

2? 3? The magical 137?

Oale said...

Ah, i meant the smallest decimal number that has some use in applied physics? Why any talk of any smaller numbers?

David in Cal said...

Very nice post, David.

David Appell said...

Thanks David.

Oale, I guess I don't know what you mean.... Planck's constant is pretty small. The Planck time is about 5e-44 seconds, and the cosmologial constant is ~ 2e-123 in Planck units.

(In Planck units, hbar, c, G and k are all set equal to one. Theorists use it because it makes their equations look much prettier.... Any result can be translated back into regular units by multiplying by the appropriate powers of hbar, c, G and k. (k is Boltzmann's constant.))

Oale said...

thank you, Dr.Appell!