Prime-Generating Formulas: Euler, Heegner, and the Ulam Spiral

The Remarkable Formula

In 1772, Leonhard Euler discovered a formula that produces an extraordinary number of consecutive primes from a single quadratic expression.

Important: Euler’s Prime-Generating Polynomial.
The quadratic
$$ P(n) = n^2 + n + 41 $$
produces prime numbers for all integers $ n $ with $ 0 \leq n \leq 39 $.

That is: one formula, forty consecutive prime outputs.

[Image: Plot of Euler’s prime-generating polynomial for n = 0 through 45, showing all outputs are prime for n = 0 to 39]

The first several values of $ P(n) = n^2 + n + 41 $:

$ n $: 0 | $ n^2 + n + 41 $: 41 | Prime?: Yes
$ n $: 1 | $ n^2 + n + 41 $: 43 | Prime?: Yes
$ n $: 2 | $ n^2 + n + 41 $: 47 | Prime?: Yes
$ n $: 3 | $ n^2 + n + 41 $: 53 | Prime?: Yes
$ n $: 4 | $ n^2 + n + 41 $: 61 | Prime?: Yes
$ n $: 5 | $ n^2 + n + 41 $: 71 | Prime?: Yes
$ n $: 6 | $ n^2 + n + 41 $: 83 | Prime?: Yes
$ n $: 7 | $ n^2 + n + 41 $: 97 | Prime?: Yes
$ n $: 8 | $ n^2 + n + 41 $: 113 | Prime?: Yes
$ n $: 9 | $ n^2 + n + 41 $: 131 | Prime?: Yes
$ n $: 10 | $ n^2 + n + 41 $: 151 | Prime?: Yes
$ n $: … | $ n^2 + n + 41 $: … | Prime?: …
$ n $: 39 | $ n^2 + n + 41 $: 1601 | Prime?: Yes
$ n $: 40 | $ n^2 + n + 41 $: 1681 = 41^2 | Prime?: No

Euler's prime-generating polynomial

Ulam spiral showing prime distribution

Why the Formula Fails at n = 40

Proposition. $ P(40) = 41^2 $ is composite. More generally, $ 41 \mid P(n) $ whenever $ 41 \mid n $ or $ 41 \mid (n+1) $.

Proof. Write $ P(n) = n(n+1) + 41 $. When $ n = 40 $:

$$ P(40) = 40 \times 41 + 41 = 41(40 + 1) = 41 \times 41 = 41^2. $$

Similarly, when $ n = 41 $:

$$ P(41) = 41 \times 42 + 41 = 41(42 + 1) = 41 \times 43. $$

In general, if $ 41 \mid n $ then $ 41 \mid n(n+1) $ and so $ 41 \mid P(n) $. If $ 41 \mid (n+1) $ then $ 41 \mid n(n+1) $ and again $ 41 \mid P(n) $.

The very constant that makes the formula work for so many values, the number 41, is precisely what forces it to fail. This is an inherent limitation of polynomial prime generators: any non-constant polynomial will eventually produce composite values.

Negative Values and the Extended Range

The formula also produces primes for negative values of $ n $.

Proposition. $ P(n) = n^2 + n + 41 $ is prime for all integers $ n $ with $ -40 \leq n \leq 39 $.

Proof sketch. Since $ P(n) = n^2 + n + 41 = (n + \tfrac{1}{2})^2 + \tfrac{163}{4} $, we have $ P(n) = P(-n-1) $. In particular, $ P(-1) = P(0) = 41 $, $ P(-2) = P(1) = 43 $, and so on. The values for $ n = -40, \ldots, -1 $ are the same as for $ n = 0, \ldots, 39 $ (in reverse order). Since all of $ P(0), \ldots, P(39) $ are prime, so are all of $ P(-40), \ldots, P(-1) $.

This means the formula produces primes for 80 consecutive integers: from $ -40 $ to 39.

An Equivalent Reformulation

Defining $ Q(m) = m^2 – 79m + 1601 $, we can verify:

$$ Q(m) = (m – 40)^2 + (m – 40) + 41 = P(m – 40). $$

So $ Q(m) $ is prime for $ m = 0, 1, \ldots, 79 $, the same 80 prime values, just reindexed.

Complete Table of Values

All 40 prime values of $ P(n) = n^2 + n + 41 $ for $ n = 0, \ldots, 39 $:

$ n $: 0 | $ P(n) $: 41 | | $ n $: 20 | $ P(n) $: 461
$ n $: 1 | $ P(n) $: 43 | | $ n $: 21 | $ P(n) $: 503
$ n $: 2 | $ P(n) $: 47 | | $ n $: 22 | $ P(n) $: 547
$ n $: 3 | $ P(n) $: 53 | | $ n $: 23 | $ P(n) $: 593
$ n $: 4 | $ P(n) $: 61 | | $ n $: 24 | $ P(n) $: 641
$ n $: 5 | $ P(n) $: 71 | | $ n $: 25 | $ P(n) $: 691
$ n $: 6 | $ P(n) $: 83 | | $ n $: 26 | $ P(n) $: 743
$ n $: 7 | $ P(n) $: 97 | | $ n $: 27 | $ P(n) $: 797
$ n $: 8 | $ P(n) $: 113 | | $ n $: 28 | $ P(n) $: 853
$ n $: 9 | $ P(n) $: 131 | | $ n $: 29 | $ P(n) $: 911
$ n $: 10 | $ P(n) $: 151 | | $ n $: 30 | $ P(n) $: 971
$ n $: 11 | $ P(n) $: 173 | | $ n $: 31 | $ P(n) $: 1033
$ n $: 12 | $ P(n) $: 197 | | $ n $: 32 | $ P(n) $: 1097
$ n $: 13 | $ P(n) $: 223 | | $ n $: 33 | $ P(n) $: 1163
$ n $: 14 | $ P(n) $: 251 | | $ n $: 34 | $ P(n) $: 1231
$ n $: 15 | $ P(n) $: 281 | | $ n $: 35 | $ P(n) $: 1301
$ n $: 16 | $ P(n) $: 313 | | $ n $: 36 | $ P(n) $: 1373
$ n $: 17 | $ P(n) $: 347 | | $ n $: 37 | $ P(n) $: 1447
$ n $: 18 | $ P(n) $: 383 | | $ n $: 38 | $ P(n) $: 1523
$ n $: 19 | $ P(n) $: 421 | | $ n $: 39 | $ P(n) $: 1601
Every entry in this table is prime.

The Connection to Heegner Numbers

The number 41 is not arbitrary. It connects to one of the deepest results in algebraic number theory through Heegner numbers.

Definition (Heegner Number). A positive integer $ d $ is a Heegner number if the imaginary quadratic field $ \mathbb{Q}(\sqrt{-d}) $ has class number 1, meaning its ring of integers is a unique factorization domain.

Theorem (Stark-Heegner, 1967). There are exactly nine Heegner numbers:

$$ 1, \quad 2, \quad 3, \quad 7, \quad 11, \quad 19, \quad 43, \quad 67, \quad 163. $$

The connection to Euler’s formula is revealed by the following result:

Theorem (Rabinowitz, 1913). The polynomial $ n^2 + n + p $ produces primes for all integers $ n = 0, 1, \ldots, p-2 $ if and only if $ 4p – 1 $ is a Heegner number.

Since $ 4 \times 41 – 1 = 163 $ is the largest Heegner number, Euler’s formula gives the longest possible prime run of this type.

The Lucky Numbers of Euler

Definition (Lucky Number of Euler). A positive integer $ p $ is a lucky number of Euler if $ n^2 + n + p $ is prime for all $ n = 0, 1, \ldots, p – 2 $.

By Rabinowitz’s theorem, there are exactly six lucky numbers of Euler:

$ p $: 2 | $ 4p – 1 $: 7 | Heegner number?: Yes
$ p $: 3 | $ 4p – 1 $: 11 | Heegner number?: Yes
$ p $: 5 | $ 4p – 1 $: 19 | Heegner number?: Yes
$ p $: 11 | $ 4p – 1 $: 43 | Heegner number?: Yes
$ p $: 17 | $ 4p – 1 $: 67 | Heegner number?: Yes
$ p $: 41 | $ 4p – 1 $: 163 | Heegner number?: Yes
Since there are exactly nine Heegner numbers and only six fit the form $ 4p – 1 $ for positive integers $ p $, there can never be another lucky number of Euler. The number 41 gives the longest possible run of primes from any polynomial of the form $ n^2 + n + p $.

Why No Polynomial Can Generate All Primes

Theorem. No non-constant polynomial $ f(n) \in \mathbb{Z}[n] $ can produce only prime values for all $ n \in \mathbb{N} $.

Proof. Suppose $ f(n_0) = p $ is prime. Then for any integer $ k $:

$$ f(n_0 + kp) \equiv f(n_0) = p \equiv 0 \pmod{p}. $$

Since $ f $ is non-constant, $ |f(n_0 + kp)| > p $ for sufficiently large $ k $. So $ f(n_0 + kp) $ is divisible by $ p $ but not equal to $ \pm p $, hence composite.

This theorem means Euler’s formula is remarkable precisely because 40 consecutive primes is so much longer than one would typically expect from a quadratic polynomial.

The Ulam Spiral Connection

In 1963, the physicist Stanislaw Ulam was doodling during a lecture and wrote integers in a spiral pattern, circling the primes. He noticed that primes tend to cluster along certain diagonal lines. This is now called the Ulam spiral.

Some of those diagonal lines correspond to quadratic polynomials, and Euler’s formula $ n^2 + n + 41 $ falls on a particularly prominent diagonal. The visual clustering of primes along these diagonals reflects the same algebraic structures that make certain polynomials effective at generating primes.

[Image: The Ulam spiral with integers arranged in a spiral pattern and primes highlighted, showing visible diagonal lines corresponding to quadratic polynomials]

In the Ulam spiral centered at 41, an unusually dense diagonal of primes appears, corresponding to the values of $ n^2 + n + 41 $. This visual pattern helped stimulate research into the distribution of primes along polynomial sequences.

Connections to Other Topics

Quadratic Residues

Euler’s polynomial $ n^2 + n + 41 $ has a discriminant of $ 1 – 4(41) = -163 $, and the quadratic residue structure of primes modulo 163 determines whether they are represented by the form $ n^2 + n + 41 $. This connects to the theory of quadratic forms and class field theory.

The Bunyakovsky Conjecture

The Bunyakovsky conjecture predicts that any irreducible polynomial with no fixed prime divisor produces infinitely many prime values. This is unproven for any polynomial of degree $ \geq 2 $. Euler’s polynomial provides striking evidence for this conjecture, but 40 primes (or even 80) do not constitute a proof.

The Class Number Problem

The fact that there are exactly nine Heegner numbers is equivalent to saying there are exactly nine imaginary quadratic fields with class number 1. This was one of the great open problems in number theory until it was settled by Stark in 1967 (confirming earlier work by Heegner). The proof requires deep results in algebraic number theory, the Baker-Heegner-Stark theorem.

The Discriminant and Why 163 Is Special

The key to understanding Euler’s polynomial lies in its discriminant. For the general quadratic $ n^2 + n + p $, the discriminant is

$$ \Delta = 1 – 4p. $$

When $ p = 41 $, we get $ \Delta = 1 – 164 = -163 $. The absolute value 163 is a Heegner number, and the ring of integers of $ \mathbb{Q}(\sqrt{-163}) $ is a unique factorization domain.

Why does unique factorization matter? When we try to factor the values of $ n^2 + n + 41 $ using ideals in $ \mathbb{Q}(\sqrt{-163}) $, the unique factorization property guarantees that norms of ideals behave predictably. If an integer represented by the form $ n^2 + n + 41 $ were composite, say $ n^2 + n + 41 = ab $, the corresponding ideal would factor non-trivially. But the class number 1 condition forces this factorization to come from principal ideals, and a careful analysis shows this is impossible when $ 0 \leq n \leq 39 $.

For discriminants where unique factorization fails (class number > 1), there are additional quadratic forms that can represent integers, creating more ways for values to be composite. This is why only the six lucky numbers of Euler, corresponding to class number 1 fields, can produce unbroken runs of primes.

Other Notable Prime-Generating Polynomials

While Euler’s $ n^2 + n + 41 $ is the champion among quadratic polynomials of its special form, other polynomials also generate many primes:

$ 2n^2 + 29 $ produces primes for $ n = 0, 1, \ldots, 28 $ (29 consecutive primes).
$ n^2 – n + 41 $ is equivalent to Euler’s polynomial shifted by one and produces the same set of 40 prime values for $ n = 1, 2, \ldots, 40 $.
$ 6n^2 + 6n + 31 $ produces primes for $ n = 0, 1, \ldots, 28 $.

No quadratic polynomial of the form $ n^2 + n + p $ can beat Euler’s record, but polynomials with different leading coefficients remain largely unexplored. Finding the “best” prime-generating polynomial of each degree is an active area of computational number theory.

The Density of Primes in Euler’s Polynomial

Even beyond $ n = 39 $, Euler’s polynomial produces primes with unusually high frequency. Among the first 10,000 values $ P(0), P(1), \ldots, P(9999) $, roughly 47% are prime. For a typical quadratic polynomial, heuristics predict a prime density around $ C/\ln x $ where $ C $ depends on the polynomial. The constant for Euler’s polynomial is exceptionally large due to the 163 connection.

The Hardy-Littlewood conjecture gives a precise prediction: the number of primes of the form $ n^2 + n + 41 $ for $ n \leq N $ should be asymptotic to

$$ \frac{C_{41}}{\sqrt{\Delta}} \cdot \frac{N}{\ln N} $$

where $ C_{41} $ is a product over primes that depends on the quadratic residue symbol of $ \Delta = -163 $.

Exercises:

Verify that $ P(n) = n^2 + n + 41 $ gives a prime for $ n = 15, 20, 25, 30, 35 $.

Show that $ P(40) = 41^2 $ and $ P(41) = 41 \times 43 $. What is the next value of $ n > 41 $ for which $ P(n) $ is composite?

For the lucky number $ p = 17 $, verify that $ n^2 + n + 17 $ produces primes for $ n = 0, 1, \ldots, 15 $. At which $ n $ does it first produce a composite?

Prove the symmetry $ P(n) = P(-n – 1) $ directly from the formula $ P(n) = n^2 + n + 41 $.

Draw a small Ulam spiral (say, integers 1 through 81 in a 9×9 grid starting from the center) and circle the primes. Can you spot any diagonal patterns?

Explain why $ n^2 + n + 41 $ can never be divisible by 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, or 37 when $ 0 \leq n \leq 39 $. (Hint: consider $ n^2 + n + 41 \bmod p $ for each small prime $ p $.)