Sunday Function

Due to some homework which is taking longer than anticipated, today's Sunday Function will have to be a bit quick. It's no less interesting for that.

Define a function Q(n) on the natural numbers, such that Q(n) = 1 for a prime number and Q(n) = 0 for a composite number. In other words, it's just a function that checks to see if a number is prime or not. If you were trying to evaluate this function by hand, you could do so by manually dividing n by all the numbers less than n to see if anything divided evenly. Actually this would be very inefficient, you only have to divide by the prime numbers less than the square root of n in order to have checked all possibilities.

Even this method of trial division is not workable for very large numbers. To see if 10100 + 1 is prime you'll have to check something in the vicinity of 1048 possible prime factors. This is obviously not a tractable problem for very large n. Fortunately there's several much more sophisticated algorithms for testing primality. You'd find out that in fact 10100 + 1 is not a prime number. Actually finding the factors is much, much more difficult in general than primality testing. It's can be done without difficulty for the number we just tried, but for much larger numbers it quickly becomes nearly impossible. Fortunately primality testing without finding factors doesn't grow in difficulty at nearly the same rate. It's "easy" in some mathematically defined sense. (The test we're about to discuss is O(p2), for the curious.)

One of those methods works very well for a class of numbers called Mersenne primes. These are prime numbers of the form 2p - 1, where p is itself a prime number. Not all numbers of that form are prime. In fact, most aren't. Now there are probably an infinite number of primes of that form, but it hasn't been formally proved yet.

This month, the Great Internet Mersenne Prime Search found the largest known prime number, a Mersenne prime with p = 43,112,609. That's a huge number, with more than ten million digits. There's probably more of them out there, and some have significant cash awards attached to them. The first prime with 100,000,000 digits will net the finder $150,000. Good luck!

More like this

Two new Mersenne primes: 243,112,609-1 and 237,156,667-1. The former is now the largest prime number known. Interestingly the larger was discovered before the former, thus winning $100,000 from the EFF for Edson Smith who installed the software which identified this Mersenne prime on a UCLA…
We've spent more than a few Sunday Function features discussing the properties of the prime numbers. They're just so important and interesting in number theory that they're an irresistible target. Let's set some scenery before getting to the actual function this week. There are an infinite number…
There's one kind of semi-mathematical crackpottery that people frequently send to me, but which i generally don't write about. Given my background, I call it gematria - but it covers a much wider range than what's really technically meant by that term. Another good name for it would be numeric…
We're doing two functions today. If I'm not mistaken we've done each of them separately, but there's a famous and interesting relationship between the two that's always interesting to look at. Like very many interesting mathematical facts, it has to do with the prime numbers. As such the first…

Isn't 10^100+1 divisible by 73? Quadratic surds and all that.

By Carl Brannen (not verified) on 28 Sep 2008 #permalink

I should probably add that 10^4 mod 73 = -1, from which the fact that 73 divides 10^100+1 is obvious.

By Carl Brannen (not verified) on 28 Sep 2008 #permalink

Quite right. I should say that sqrt(n) trial divisions are the worst case scenario for the trial division test. Very many numbers will have their first prime factor early on. In this case, Mathematica tells me the first few factors (there are 8 total) are 73, 137, 401, 1201, and 1601. The highest before the root n cutoff is only around 5.9x10^9.

There is some confusion about the conditions of the Cash Prize. Is it for the first PRIME Number of over 10M
digits? Or, for the first MERSENNE PRIME over 10M digits?
How long is the so far known PRIME Number, Mersenne or
non-Mersenne, before the present nearly 13M digits number?

By Mathateur (not verified) on 29 Sep 2008 #permalink

Mathateur: I don't know whether the cash prize requires the prime to be a Mersenne prime, but it almost certainly will be. Most of the largest known primes are Mersenne primes, for the simple reason that with Mersenne primes you have a good idea of where to look. If you are hunting for general category primes, you have to either get lucky or search systematically, and the latter procedure is one order of N more computationally intensive (because in effect you have to test all numbers in the region of interest) than testing whether a candidate Mersenne number of similar magnitude is prime.

By Eric Lund (not verified) on 29 Sep 2008 #permalink

Eric Lund: Good explaining.Have any body got the first 10 digits of the new 13M number?

By Mathateur (not verified) on 29 Sep 2008 #permalink