Figure 1. The Prime Spiral, starting with 41 at the center.
Ed Pegg Jr., July 17, 2006
"Jeserac sat motionless within a whirlpool of numbers. The first thousand primes.... Jeserac was no mathematician, though sometimes he liked to believe he was. All he could do was to search among the infinite array of primes for special relationships and rules which more talented men might incorporate in general laws. He could find how numbers behaved, but he could not explain why. It was his pleasure to hack his way through the arithmetical jungle, and sometimes he discovered wonders that more skillful explorers had missed. He set up the matrix of all possible integers, and started his computer stringing the primes across its surface as beads might be arranged at the intersections of a mesh." Arthur C. Clarke, The City and the Stars, 1956.
Sir Clarke wondered if the above would get him credit for the Prime Spiral, an object normally attributed to Stanislaw Ulam. In 1963, Dr. Ulam doodled a spiral of numbers during a boring meeting, circled the primes, and noticed they were like beads on a string. Martin Gardner made the Ulam prime spiral famous in his column "Patterns and Primes." Unfortunately for Sir Clarke, just like geostationary satellites, he didn't actually construct the experiment. Still, his guess at the primes aligning like beads seems remarkably prescient. Predating them both, in 1932, Laurence M. Klauber presented a paper to the Mathematical Association of America, giving a method for finding prime generating polynomials via a spiral grid. Klauber's primary profession was the study of rattlesnakes. So, sorry Sir Clarke and Dr. Ulam, I have to give the nod to Mr. Rattlesnake for the prime spiral idea. Ironically, the pattern matching technique Klauber used on prime spirals parallels his use of mathematical statistics on the patterning of living rattlesnakes, which was a major breakthrough in herpetology.
If Clarke, Ulam, or Klauber had started with 41, they would have gotten a grid like the following:
Figure 1. The Prime Spiral, starting with 41 at the center.
That long string of circled primes on the diagonal, in sequence, is 41, 43, 47, 53, ..., 1523, 1601. A polynomial that produces the same result, first discovered by Euler, is x2 - x + 41. Polynomials like this, which generate long strings of primes, are called prime generating polynomials.
The polynomial x2 - x + 41 has many properties. Quoting MathWorld's Heegner number entry: "The Heegner numbers have a number of fascinating connections with amazing results in prime number theory. In particular, the j-function provides stunning connections between e, π, and the algebraic integers. They also explain why Euler's prime-generating polynomial x2 - x + 41 is so surprisingly good at producing primes." Since this simple polynomial leads into such things as Monstrous Moonshine, i've wondered: Do other prime generating polynomials have rich properties?
Unfortunately, beyond prime arithmetic progressions, the field didn't seem well-explored. In pre-2005 mathematical history, only two polynomials bested Euler's in terms of generating distinct primes. Fung and Ruby together found 36x2 - 810x + 2753 (45 distinct primes) and 47 x2 - 1701 x + 10181 (43 distinct primes). In 2005, Ruiz found 3x3 - 183x2 + 3318x - 18757 (43 distinct primes), and Speiser found 103x2 - 4707x + 50383 (43 distinct primes). I suggested the problem to Al Zimmermann's Programming Contests, which frequently shatters mathematical records. The problem got selected, and over a hundred programmers worked on it.
The Al Zimmermann prime generating polynomial contest is now over. Results have been posted. All known records were shattered. Of particular note is the polynomial (x5 - 133x4 + 6729x3 - 158379x2 + 1720294x - 6823316)/4, which generates 57 distinct primes. It was first discovered by Shyam Sunder Gupta, and then subsequently rediscovered by three other programming teams. The team Jaroslaw Wroblewski and Jean-Charles Meyrignac were the overall winners of the contest. I stop at order 6 polynomials here. For orders up to 10, see the results page.
|
Is there any incredible math hidden within these polynomials? ("All+" means that all the primes are positive. "Int?" indicates that all the polynomial coefficients are integers. "#dist" is the number of distinct primes generated in the range x=0 to n, where n is the first value to generate a non-prime.)
When might a polynomial produce a prime? Obviously, the polynomial must be unfactorable / irreducible. x2 - 2x + 1 = (x + 1)(x + 1) won't be prime for any integer x. Irreducible polynomials like 3x2 - x + 2 are always divisible by 2. For any irreducible polynomial, we can consider the same polynomial divided by the greatest common divisor of the first two integer values.
Figure 3. The Bouniakowsky polynomial, for irreducible f(x).
Any Bouniakowsky polynomial produces an infinite number of primes (Bouniakowsky conjecture, 1857). Not much progress has been made on this conjecture. Dirichlet's Theorem (1837) proves the conjecture is true for a x + b. That's it, that's all that's known. So far, every Bouniakowsky polynomial that has been tested has produced multiple primes. No Bouniakowsky polynomial has been proven to produce an infinite number of primes. Some prime-poor cases are known, like x12 + 488669, which doesn't produce a prime until x = 616980. Prime-rich polynomials are also known, like Steve Trevorrow's x2 + 1151x - 1023163, which produces 699 primes in the range 0 to 1000.
If (x5 - 133x4 + 6729x3 - 158379x2 + 1720294x - 6823316)/4 has some amazing connections to other branches of mathematics, please let me know. Many congratulations to the participants of the prime polynomial contest, for making math history. A belated congratulations to Mr. Rattlesnake. His prime spiral pattern spotting skills have been overlooked for far too long.
Arthur C. Clarke, The City and the Stars, 1956.
Martin Gardner, "Patterns and Primes." Martin Gardner's Mathematical Games, MAA, 2005.
Jean-Charles Meyrignac, "Al Zimmermann Programming Contests: Prime Generating Polynomials Final Report." July 9, 2006. http://euler.free.fr/contest/PGPReport.htm.
Eric W. Weisstein. Bouniakowsky Conjecture, Dirichlet's Theorem, Heegner Number, Monstrous Moonshine, Prime Arithmetic Progression, Prime-Generating Polynomial, Prime Spiral, From MathWorld--A Wolfram Web Resource.
Wikipedia, "Laurence M. Klauber." http://en.wikipedia.org/wiki/Laurence_M._Klauber.
Comments are welcome. Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.
Ed Pegg Jr. is the webmaster of mathpuzzle.com. He works at Wolfram Research, Inc. as an associate editor of MathWorld. He is also a math consultant for the TV show Numb3rs.