A New Formula for Generating Primes

Some simple expressions can generate a surprisingly large number of primes, whole numbers that are evenly divisible only by themselves and 1. The remarkable formula x² + x + 41, for example, yields an unbroken string of 40 primes, starting at x = 0.

Another simple, prime-rich formula, x² + x + 17, generates prime numbers for all integer values of x from 0 through 15. Searching for a polynomial formula that produces all primes, however, would be fruitless. Mathematicians proved years ago that no polynomial expression with integer coefficients has only prime values.

But there are other possibilities. So people have continued to look for simple prime-generating functions, and Rutgers graduate student Eric Rowland has just found a new one. In a paper published in the Journal of Integer Sequences, Rowland defines his formula and proves that it generates only 1s and primes.

"Blending simplicity and mystery, Eric Rowland's formula is a delightful composition in the music of the primes, one everyone can enjoy," Jeffrey Shallit recently commented on his "Recursivity" blog. A professor at the University of Waterloo, Shallit is editor of the Journal of Integer Sequences.

Here's Rowland's recursive formula for generating primes, as presented by Shallit in his blog.

Define a(1) = 7.
For n greater than or equal to 2, set a(n) = a(n – 1) + gcd(n, a(n – 1)). Here "gcd" means the greatest common divisor.

For example, given that a(1) = 7, a(2) = a(1) + gcd(2, 7) = 7 + 1 = 8.

The prime generator is then a(n) – a(n – 1). The resulting numbers are the so-called first differences of the original sequence.

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
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

Ignoring the 1s, we find that Rowland's formula generates the primes 5, 3, 11, 3 (again), and 23. If we continue the process and remove duplicates, the formula generates the prime sequence 5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559, 15131, 53, 30323, . . .

Rowland describes his formula in the "A New Kind of Science" blog. He notes that the formula originated in 2003 at the NKS summer school, where participants discover and explore computational systems that exhibit "interesting" behavior.

"This was a surprising discovery, since previously there was no known reliable prime-generating formula that wasn't expressly engineered for this purpose," Rowland said. Rowland went on to prove mathematically that this recurrence produces only 1s and primes. He has created a Mathematica demonstration for exploring the recurrence.

Rowland's formula is unlikely to lead to more efficient ways of generating large primes, a crucial operation in cryptography. His formula produces the prime p only after first generating (p – 3)/2 1s. "So it takes a really long time to generate a large prime," Shallit said. Rowland "has a method for skipping over those useless 1s, but doing so essentially requires an independent test for primality."

Are there other formula's like Rowland's? Recently, French mathematician Benoit Cloitre proved that by setting b(1) = 1 and b(n) = b(n – 1) + lcm(n, b(n – 1)) for n greater than or equal to 2, b(n)/b(n – 1) – 1 is either 1 or prime.

Many other questions remain. Is there anything special about the choice of a(1) = 7? Does Rowland's formula eventually generate all odd primes? Rowland suspects that it does, but there's much more to learn.