The Doodle That Sees the Primes

I · The doodle

At a scientific meeting in 1963, sitting through what he described as a “long and very boring paper”, Stanisław Ulam began to doodle. He wrote 1 in the middle of the page, then spiralled the counting numbers outward around it: 2 to the right, 3 above that, 4 and 5 to the left, and on, square ring after square ring. Then he circled the primes.

He expected nothing. On the number line the primes, 2, 3, 5, 7, 11, 13, have irregular gaps. But circled on the spiral they did something startling: they lined up on the diagonals. Whole diagonal streets ran thick with primes; others stayed nearly empty. Ulam went home, had the spiral plotted by computer out to tens of thousands, and the diagonals only sharpened. Martin Gardner put the picture on the cover of Scientific American in March 1964, and it has unsettled people ever since.

Here is the spiral, drawn live in your browser. Every prime up to 40,401 is a dark cell; the composites are left blank. Look at it for a moment before reading on — the diagonals are not subtle.

II · Why diagonals at all

The first half of the mystery dissolves the moment you ask what a diagonal is. Walk outward along a diagonal ray of the spiral and eventually the numbers grow by a fixed, widening stride, the signature of a quadratic. Tap any of the four central rays above and the instrument fits the formula from the centre: it is always 4n² + bn + c for integers b, c and n ≥ 0. The southwest ray is 4n²+2n+1; the northeast is 4n²−2n+1; the southeast holds the odd squares (2n+1)². Offset rays can have an initial stretch before they settle into one of these parabolic strings.

That already explains the grid of the pattern. An outward horizontal or vertical ray also eventually follows a quadratic, but its values alternate odd and even. Each diagonal keeps one parity: all odd or all even. An even number bigger than two is never prime, so half the board is dead on arrival. The primes, except 2, have nowhere to live but the odd diagonals. So some diagonal preference is forced, and unmysterious.

What is not explained is why some odd diagonals blaze with primes and their neighbours stay dim. Two parabolas, both all-odd, can differ wildly in how many primes they catch. That is the real question Ulam’s doodle asks, and it turns out to be the same question Euler asked in 1772 — and the same question that is still, in its general form, unsolved.

III · Euler’s forty-prime opening run

In 1772 Leonhard Euler noticed something about the humble polynomial n² + n + 41. Feed it n = 0 and you get 41, a prime. n = 1 gives 43, prime. Then 47, 53, 61, 71, 83, 97… It keeps producing primes — not for a while, but for forty values in a row, n = 0 through 39, ending at 39²+39+41 = 1601. Only at n = 40 does it finally fail, and it fails for a reason you can see at a glance: 40²+40+41 = 1681 = 41². The streak had to die exactly there, because 40²+40+41 = 41·(40+1) — once n = 40, the 41 divides it.

Forty primes from one little parabola is not luck you can shrug off. A random odd number near 1000 is prime about one time in three and a half; Euler’s polynomial hits forty for forty. Across the first ten thousand values it is prime 41% of the time. Drop it onto a spiral and it would be one of those blazing diagonals. So the spiral’s riddle and Euler’s polynomial are the same riddle: what makes a quadratic prime-rich?

Try it. Pick the constant c in n²+n+c and the lab below runs the polynomial, lights every prime it produces, and tells you how long the opening run of primes lasts. Euler’s 41 is the largest constant that gives the full c−1 opening run; most values of c are mediocre. The pattern in which values win is the whole secret, and it is exact.

IV · The exact reason: Rabinowitsch, 1913

Run the lab across many values of c and a strange roster of winners emerges: a full run of primes — every value from n=0 to n=c−2 prime — happens only for c = 2, 3, 5, 11, 17, 41. These are Euler’s lucky numbers, and there are exactly six of them. Nothing larger ever works again. Why those, and why no more?

The answer, presented by Georg Rabinowitsch in 1912 and published in 1913, reaches into a different country of mathematics entirely. To a quadratic like n²+n+c you can attach a single number, its discriminant 1 − 4c; for Euler’s polynomial, 1 − 164 = −163. That negative number names an imaginary quadratic field, the number system you get by adjoining √(1−4c) to the ordinary fractions. And every such system has a single integer fingerprint called its class number, which measures how badly unique factorization fails in its ring of integers, how far the system is from a world where every number factors into primes in one and only one way. Class number 1 means factorization is perfectly unique, just like the ordinary integers; bigger class numbers mean it breaks.

Rabinowitsch’s theorem. For an integer c ≥ 2, the polynomial n²+n+c is prime for all of n = 0 … c−2 if and only if 4c−1 is squarefree and the field ℚ(√(1−4c)) has class number 1. With that squarefree condition, the visible miracle of the full opening run is exactly the invisible miracle of factorization staying unique in the field’s ring of integers. The lab computes the field’s class number live, by counting reduced quadratic forms at its fundamental discriminant, and tests squarefreeness separately.

V · The nine numbers, and why there is no luckier polynomial

Now the roster of lucky numbers stops being mysterious and becomes a census. Euler’s lucky c = 2, 3, 5, 11, 17, 41 are precisely the primes whose squarefree discriminant 1−4c, that is, −7, −11, −19, −43, −67, −163, names a field of class number one. So the question “is there a polynomial luckier than Euler’s?” becomes “is there an imaginary quadratic field of class number one with a more negative discriminant than −163?”

There is not. The full list of positive squarefree d for which ℚ(√−d) has class number one is one of the famous finite lists in mathematics: the nine Heegner numbers:

1, 2, 3, 7, 11, 19, 43, 67, 163

and that is all of them, forever. Carl Friedrich Gauss conjectured the list around 1801; Kurt Heegner proved it in 1952 (and was disbelieved for more than a decade over a gap later shown to be reparable); Alan Baker and Harold Stark independently nailed it shut in 1966–67. 163 is the last and largest. So Euler’s n²+n+41, born of −163, has the largest constant c that gives a full c−1 opening run in the family n²+n+c. No c > 41 makes every value from n=0 through c−2 prime.

The same 163 is the reason behind a second, gaudier coincidence: e^π√163 is almost exactly a whole number, 262 537 412 640 768 744 minus about 0.00000000000075 — close enough that it fooled people into thinking it was an integer, and earned the nickname Ramanujan’s constant. (The gap is far too small for the ordinary 64-bit arithmetic in this page to even see; the value below is what your browser computes, rounded, and it differs from the true value by hundreds — an honest reminder of where double precision runs out.) That near-miss is class number one again, viewed through a different window. The bored doodle, the forty primes, and the almost-integer are three faces of a single deep fact.

VI · The half that is still open

It would be a tidy story if class numbers explained the whole spiral. They do not. Rabinowitsch settles which n²+n+c have the full c−1 opening run, including Euler’s forty-in-a-row. But the spiral’s blazing diagonals are about something looser and harder: not “primes with no gaps at the start,” but “unusually many primes, forever.” How dense are the primes along a given parabola, all the way out to infinity?

For that, the best we have is a conjecture. In 1923 G. H. Hardy and J. E. Littlewood wrote down a precise prediction, their Conjecture F, for the density of primes taken by an irreducible quadratic with integer coefficients, positive leading coefficient, and no prime dividing every value. For Euler’s polynomial it forecasts a prime crop about 6.6 times richer than random integers of the same size predict, and when you actually count out to a million, the forecast is dead on: the measured factor is 6.64. The prediction works beautifully.

That is the honest shape of it. The part that bottoms out in a proof (why Euler’s opening run is exactly forty, why no larger c gives the full c−1 run) runs through class numbers and the nine Heegner numbers and is as solid as anything in the subject. The part the spiral most wants you to ask, why the diagonals stay bright forever, is a frontier, and the frontier is where the verifying stops and the marking-as-unknown begins.