Built on Facts

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¹⁰⁰ + 1 is prime you’ll have to check something in the vicinity of 10⁴⁸ 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¹⁰⁰ + 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²), 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!

Comments

#1 Carl Brannen
September 28, 2008

Isn’t 10^100+1 divisible by 73? Quadratic surds and all that.
#2 Carl Brannen
September 28, 2008

I should probably add that 10^4 mod 73 = -1, from which the fact that 73 divides 10^100+1 is obvious.
#3 Matt Springer
September 28, 2008

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.9×10^9.
#4 Kobra
September 28, 2008

print “Prime” if (1 x shift) !~ /^1?$|^(11+?)\1+$/

Solved.
#5 Adrian Morgan
September 29, 2008

Speaking of prime numbers, I wouldn’t mind some informed feedback on a blog post of mine from November 2006, if anyone wants to discuss obscure observations about prime numbers with an intellectually curious non-expert.
#6 Mathateur
September 29, 2008

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?
#7 Eric Lund
September 29, 2008

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.
#8 Mathateur
September 29, 2008

Eric Lund: Good explaining.Have any body got the first 10 digits of the new 13M number?
#9 Nemo
September 30, 2008

x^5 + 1 = (x + 1) * (x^4 – x^3 + x^2 – x + 1)

Let x=10^20. QED.

Bad example.