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 x^{2}  x + 41. Polynomials like this, which generate long strings of primes, are called prime generating polynomials.
The polynomial x^{2}  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 jfunction provides stunning connections between e, π, and the algebraic integers. They also explain why Euler's primegenerating polynomial x^{2}  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 wellexplored. In pre2005 mathematical history, only two polynomials bested Euler's in terms of generating distinct primes. Fung and Ruby together found 36x^{2}  810x + 2753 (45 distinct primes) and 47 x^{2}  1701 x + 10181 (43 distinct primes). In 2005, Ruiz found 3x^{3}  183x^{2} + 3318x  18757 (43 distinct primes), and Speiser found 103x^{2}  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 (x^{5}  133x^{4} + 6729x^{3}  158379x^{2} + 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 JeanCharles 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 nonprime.)
When might a polynomial produce a prime? Obviously, the polynomial must be unfactorable / irreducible. x^{2}  2x + 1 = (x + 1)(x + 1) won't be prime for any integer x. Irreducible polynomials like 3x^{2}  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 primepoor cases are known, like x^{12} + 488669, which doesn't produce a prime until x = 616980. Primerich polynomials are also known, like Steve Trevorrow's x^{2} + 1151x  1023163, which produces 699 primes in the range 0 to 1000.
If (x^{5}  133x^{4} + 6729x^{3}  158379x^{2} + 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.
JeanCharles 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, PrimeGenerating Polynomial, Prime Spiral, From MathWorldA 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.