Ulam's spiral and the diagonals of primes Image: Cortexd, Wikimedia Commons (public domain)

Ulam's spiral and the diagonals of primes

In 1963 Stanislaw Ulam, the mathematician who had worked on the Manhattan Project and on the Monte Carlo method, sat through a long and uninteresting paper at a scientific meeting and passed the time by writing the integers in a square spiral: 1 in the middle, 2 to its right, 3 above that, then 4, 5 to the left, 6, 7 below, 8, 9, 10 to the right, and so on outwards. He circled the primes. They seemed to lie along diagonal lines. Ulam, Myron Stein, and Mark Wells at Los Alamos then plotted the spiral by computer out to 65,000 and published the pictures in the American Mathematical Monthly in 1964; one of them was the cover of Scientific American in March of that year, and the Ulam spiral has been a favourite of mathematical doodlers ever since.

What the eye sees

A picture of the first 40,000 integers with the primes marked as dots shows a grainy field with clear diagonal streaks, some dense with primes and some almost empty, and fainter horizontal and vertical lines. The streaks are not an illusion, and the explanation is short.

Walk along a diagonal of the spiral and write down the numbers you pass. Along one of them you find 1, 3, 13, 31, 57, 91, ...; along another, 5, 19, 41, 71, 109, .... The differences between consecutive terms are 2, 10, 18, 26, 34, ... in the first case and 14, 22, 30, 38, ... in the second: they grow by 8 each time. A sequence whose second differences are constant is a quadratic polynomial, and indeed the first diagonal is 4n² - 2n + 1 and the second is 4n² + 2n - 1 for n = 1, 2, 3, .... Every diagonal, and every horizontal and vertical line in the spiral, is the set of values of some polynomial 4n² + bn + c.

So the question "why do the primes line up on diagonals" becomes "why do some quadratic polynomials produce more primes than others", and that is a question with partial answers.

Euler's polynomial

The famous example is older than the spiral by two centuries. Euler noticed in 1772 that n² + n + 41 is prime for every n from 0 to 39: the values are 41, 43, 47, 53, 61, 71, 83, 97, 113, 131, and so on up to 1601. At n = 40 the pattern breaks, since 40² + 40 + 41 = 41 × 41, and at n = 41 the value is 41 × 43. Forty primes in a row from a formula is a lot; the polynomial keeps producing primes at a high rate for ever after, 581 primes among its first thousand values against about 80 for a random set of numbers of that size. In Ulam's spiral, if you start the spiral at 41 instead of 1, Euler's polynomial becomes one of the main diagonals, and that diagonal is a solid line of primes for forty steps. No polynomial of degree one or more produces only primes, which is easy to prove: if f(n) is a polynomial with integer coefficients and f(a) = p, then f(a + kp) is divisible by p for every k, so the polynomial takes composite values unless it is constant.

Why does n² + n + 41 do so well? Because its values are never divisible by any of the small primes 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, or 37. For a prime q to divide n² + n + 41 for some n, the discriminant 1 - 164 = -163 must be a square modulo q, and quadratic reciprocity, the subject of Unit 10 of the masterclass, says that -163 is a non-residue modulo every prime below 41. A number that dodges all the small primes is far more likely to be prime, and the polynomial dodges them by construction. The deeper reason that -163 behaves so well is that the number field built from the square root of -163 has class number 1, the last of the nine such fields, which is the excursion of Unit 11 on Heegner numbers.

The Hardy-Littlewood prediction

In 1923 Hardy and Littlewood conjectured a formula for how many primes a given quadratic polynomial produces up to a bound, their Conjecture F. It says the count is about a constant times the integral of 1/ln t, like the prime number theorem, with the constant depending on which small primes the polynomial avoids: a factor for each prime q that is larger than 1 if q never divides the values and smaller if q divides them often. For n² + n + 41 the constant is large, about 6.6 when compared with a random set of numbers of the same size, and the prediction matches the counts. For a polynomial such as 4n² - 2n + 1, which corresponds to one of Ulam's diagonals, the constant is different, and the diagonals that look dense in the picture are exactly the ones with a large constant. The pattern in the spiral is Conjecture F drawn as a picture.

The conjecture is unproved. It is not even known whether any quadratic polynomial produces infinitely many primes; the simplest case, n² + 1, is one of Landau's four problems from 1912, all of which are open. What is proved is weaker: Iwaniec showed in 1978 that n² + 1 is infinitely often a product of at most two primes, by sieve methods, and Friedlander and Iwaniec showed in 1998 that a² + b⁴ is prime infinitely often, which is a polynomial in two variables and the subject of the research spotlight of Unit 15 of the masterclass.

Variations

The spiral can be drawn differently and the lines survive. Robert Sacks in 1994 placed the integers on an Archimedean spiral, with the perfect squares on one ray, and the primes then fall on curves that are again quadratic polynomials, with Euler's polynomial as one prominent curve. Klauber's triangle of 1932, which predates Ulam, writes the integers in rows of increasing length and shows the same diagonals. In every arrangement in which the integers along a line form a quadratic sequence, the lines appear, because they are a fact about polynomials and not about the drawing.

A different picture is in the cover image of this article: the integers to 100,000 in the spiral, coloured by the number of divisors rather than by primality. The primes are the faint background with two divisors each, the bright points are the highly composite numbers, and the diagonals are still visible because the number of divisors is also governed by which small primes divide the values on each line.

What to make of it

Ulam's spiral is often presented as a mystery, and in the strict sense it is, since the conjecture that explains it is unproved. In another sense it is well understood: the lines are quadratic polynomials, the dense ones avoid small primes, and the Hardy-Littlewood constant predicts their density to within the statistical noise. The thing nobody can do is prove that any single line contains infinitely many primes, which puts the spiral in the same place as the twin prime conjecture, as a pattern everyone believes and nobody has proved.

Unit 3 of the masterclass, free to read as the sample unit, draws the spiral next to the sieve and shows the primes thinning out along the number line; Unit 12 explains the random model of the primes from which the Hardy-Littlewood constants come, and Unit 10 supplies the reciprocity that makes 41 special. The spiral itself takes ten minutes and a sheet of squared paper, and it is worth doing once by hand before looking at the computer picture.

Study the integers properly

The NT Masterclass: weekly units, quizzes, a final exam, and a certificate.
About the program
Keep reading

Related articles