# Prime-Generating Functions

In the eighteenth century the supercomputers we have today which people can use to find prime numbers did not exist. Mathematicians have always sought to create order in a very chaotic world. Many people looked for a way to produce prime numbers. Is there a polynomial that when inputted with the set of all non-negative integers, would always produce distinct prime numbers?

In 1772 Euler discovered a polynomial whch produces primes from integers. This polynomial is x^2+x+41. After running this polynomial through Sage, we find that it does indeed produce distinct prime numbers but only for all integer values of x between 0 and 39. After that, the formula begins to degrade and not always produce prime numbers.

{41,43,47,53,61,71,83,97,113,131,151,173,197,223,251,281,313,347,383,421,461,503,547,593,641,691,743,797,853,911,971,1033,1097,1163,1231,1301,1373,1447,1523,1601}

If we then look at a second polynomial, x^2-79x+1601, and find its outputs with Sage, we find that it produces primes for all integer values between 0 and 79. Though, this polynomial simply outputs all primes that Euler’s original formula produced, twice each.

These quadratic polynomials both do pretty well. They both produce uninterrupted strings of primes of lengths 40 and 80, respectively. To show that there are polynomials that do a very poor job of this, we can look at x^2 + x + 2. The largest string of primes this produces for non negative integers is… 1, as it produces a 2 at x = 0, and nonprime numbers otherwise.

The fact is that there does not exist a polynomial with integer coefficients that always produces prime numbers. Their behavior is very difficult to predict. So although primes cannot be described with a polynomial, maybe there are other things we can learn about them by observing their distributions, another time.

## 3 thoughts on “Prime-Generating Functions”

1. Pingback: The Sieve of Eratosthenes | MATH 287

2. Samuel Coskey

Very nice post. The prime generating quadratics are certainly a surprise to find!

The big question one would ask following this post: how do you *know* there aren’t any polynomials that generate primes for *all* x?