Rutgers Graduate Student Finds New Prime-Generating Formula

Studying prime numbers is like playing the guitar. No, really, let me explain.

The guitar is a simple instrument: six strings, some frets, a sound hole. You strum with the right hand, and form chords with the left. What could be simpler? Any reasonably coordinated person can learn to play a simple song, such as "Heart of Gold", passably in a few hours.

In the same way, the prime numbers have a simple definition: the integers greater than 1 that are divisible only by themselves and 1. Any reasonably intelligent person can learn to test a small number for primality, or understand Euclid's proof that there are infinitely many prime numbers, in a short amount of time.

Yet the guitar is also fiendishly difficult. Those studying classical guitar know well how some pieces take hundreds of hours to master. Techniques such as tremolo might take years, especially if you start learning as an adult.

In the same way, the prime numbers contain within them enough subtlety that many problems remain unsolved after hundreds of years. Goldbach conjectured in 1742 that every even number greater than 2 is the sum of two primes, and today this conjecture is still unsolved. (It is known to hold for every even number less than 10¹⁸.) And a proof of the Riemann hypothesis, which would have extremely important consequences for the distribution of primes, will net you a million dollars from the Clay Mathematics Institute -- probably more than you'll get from appearing on American Idol.

For a long time mathematicians have sought a simple formula that would generate all the prime numbers, or even infinitely many distinct prime numbers. Some have even gone so far as to claim that no such formula exists -- a statement of very questionable veracity that depends entirely on one's definition of "formula". If you define formula to mean "polynomial with integer coefficients", then it's not hard (and I leave it as a challenge to the reader) to prove that no such polynomial can generate only primes, other than the trivial example of a constant polynomial. Euler's polynomial x² + x + 41 comes close: it generates primes for x = 0, 1, 2, ..., 39, but fails at x = 40.

A slight variation, though, leads to a genuine prime-generating polynomial. It is a consequence of the Davis-Matiyasevich-Putnam-Robinson work on Hilbert's 10th problem that there exists a multivariate polynomial with integer coefficients that takes on only negative and prime values when integers are substituted for the variables, and every prime is generated by some choice of the variables. In 1976, Jones, Sato, Wada, and Wiens actually wrote down such a polynomial. It has 26 variables.

Another prime-generating formula comes from a 1947 paper of W. H. Mills. Mills proved that there exists a real number A such that [ A³ⁿ ] is a prime number for all integers n ≥ 1. Here [ x ] is the greatest integer function, the greatest integer ≤ x. Unfortunately, nobody knows a good way to calculate A other than testing the numbers the formula is supposed to generate for primality, and then constructing A by working backwards.

So many people have worked on the prime numbers that it seems unlikely that there could be a simple prime-generating function that has been overlooked until now.

Rutgers graduate student Eric Rowland has defied the odds, however, and has found a new one. In a paper just published in a journal I edit, the Journal of Integer Sequences, Rowland defines his formula and proves it generates only 1's and primes. (1 is generally not accepted as a prime number, for a variety of reasons. For one thing, if 1 were a prime, then positive integers would not have a unique factorization into primes.) To be precise, I should say that the unusual property of the formula was originally conjectured by a team led by Matt Frank at a mathematics summer school in 2003 where Rowland was attending, but it was not proved until now.

Here is Rowland's formula. We define a(1) = 7, and for n ≥ 2 we set

a(n) = a(n-1) + gcd(n,a(n-1)).

Here "gcd" means the greatest common divisor. So, for example, we find a(2) = a(1) + gcd(2,7) = 8. The prime generator is then a(n) - a(n-1), the so-called first differences of the original sequence.

For example, here are the first 23 values of the a sequence:
7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69

and here are the first differences of these values:
1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23

If we ignore the 1's, then, the Rowland formula starts by generating the primes 5, 3, 11, 3 (again), and 23. The reader can easily program up the formula and find lots more primes. Removing duplicates, the first few are
5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559, 15131, 53, 30323, ...

Why does it work? The proof is too involved to give here, but it is not that difficult. The interested reader can go to Rowland's paper for the details.

Rowland has been involved with mathematics for some time. He attended UC Santa Cruz and graduated with highest honors in math in 2003. Since then he has been a graduate student at Rutgers University, studying with Doron Zeilberger. Rowland describes himself as an "experimental mathematician", and uses the computer algebra system Mathematica for his experiments. Rowland tells me that he tried to prove the formula from time to time over a four-year period, but once the crucial insight was found, "I had an outline of the proof within a few days and all the details within a few weeks."

Are there any other formulas like Rowland's? Apparently yes. Benoit Cloitre, a French mathematician, recently proved that if you set b(1) = 1 and

b(n) = b(n-1) + lcm(n,b(n-1)) for n ≥ 2,

then b(n)/b(n-1)-1 is either 1 or prime for all n ≥ 2.

Will Rowland's formula lead to more efficient ways to generate large primes? If so, cryptographers would love it. But it seems unlikely. As Rowland explains in his paper, his formula only produces the prime p after first generating (p-3)/2 1's, so it takes a really long time to generate a large prime. He has a method for skipping over those useless 1's, but doing so essentially requires an independent test for primality.

Are there still unsolved properties of Rowland's prime generator? Yes. For example, is there anything special about the choice a(1) = 7? Other choices, such as a(1) = 8, always generate primes and 1's, but others, such as a(1) = 532, do not. (This choice generates 9 after less than 20 steps.) However, Rowland conjectures that for each starting value of a(1), there exists a point after which the first differences are always either 1 or prime. Rowland also doesn't know if his formula eventually generates all odd primes, although he believes it probably does.

Rowland has a number of other projects in the works. He told me, "I'm working on several things, mostly trying to finish up a backlog of papers. But one newer project is putting bounds on the frequency of 1's in the Kolakoski word. Another is something I'm not ready to fully divulge, but it has to do with values of the p-adic logarithm. A longer term project of mine is extending what is known about the arithmetic of Pascal's triangle modulo m and, generally, additive cellular automata."

What problem would Rowland most like to solve? "I'd really like to solve the 3n+1 problem, because I think it would tell us something very interesting about representations of integers. Dividing by 2 in base 2 just means dropping the last 0, and mapping n -> 3n+1 in base 3 just means appending 1. The problem is that we don't know how to get these two bases to talk to each other -- and of course perhaps there isn't a way -- but a solution to the 3n+1 problem might show us how to do this."

Solving the 3n+1 problem would indeed be a great achievement. In the meantime, however, he can take pleasure in his prime formula. Blending simplicity and mystery, Eric Rowland's formula is a delightful composition in the music of the primes, one everyone can enjoy.

Update, July 31 2008: Rowland has his own post describing his discovery.