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 10^{100} + 1 is prime you’ll have to check something in the vicinity of 10^{48} 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 10^{100} + 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(p^{2}), 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 2^{p} – 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!