The Ulam Spiral, Seeing the Primes, math that surprises you lesson

Write $1$ in the middle of a sheet of squared paper, wind the next whole numbers around it in a square spiral, and mark every prime. The marks gather along diagonal lines, although the primes themselves come at irregular spacings. Where do the streaks come from, and does some line hold only primes? This page builds the spiral, shows that the numbers on each diagonal are the values of a quadratic polynomial, uses divisibility to explain why some diagonals are crowded with primes and others hold none, and shows why a formula that gives forty primes in a row still proves nothing about the next value.

Key terms

Ulam spiral

Definition The Ulam spiral places the positive whole numbers in the squares of a grid, one number per square. The number $1$ goes in a center square and $2$ in the square to its right. After that the path turns left, a quarter turn counterclockwise, whenever the square on its left is still empty, and otherwise goes straight on. So $3$ sits above $2$ , then $4$ and $5$ go to the left, $6$ and $7$ go down and $8$ and $9$ go to the right, which completes the first ring around $1$ at its lower right corner. Then the primes are marked. In a large spiral the marks cluster along diagonal lines, for two reasons. Every diagonal line holds only odd numbers or only even numbers, so half of the diagonals hold no prime except $2$ . And far enough from the center, the numbers on a diagonal line are the values of a quadratic polynomial, whose divisibility properties make some of the odd diagonals rich in primes and others poor. The picture raises good questions about primes, but it proves nothing about all of them. It is named after the mathematician Stanisław Ulam, who drew it in 1963.

In plain words Coil the counting numbers around a center and color the primes. The coil lines up numbers that follow simple formulas, and some of those formulas are friendlier to primes than others.

Example Here are the first two rings, the numbers $1$ to $25$ , with the primes in bold.

\begin{array}{ccccc} \mathbf{17} & 16 & 15 & 14 & \mathbf{13} \\ 18 & \mathbf{5} & 4 & \mathbf{3} & 12 \\ \mathbf{19} & 6 & 1 & \mathbf{2} & \mathbf{11} \\ 20 & \mathbf{7} & 8 & 9 & 10 \\ 21 & 22 & \mathbf{23} & 24 & 25 \end{array}

Color the grid like a checkerboard with $1$ on a dark square. Each step of the path moves to a neighboring square, which has the other color, and changes the number by $1$ . So the odd numbers all sit on dark squares and the even numbers on light ones. A diagonal line stays on one color, and a line of light squares, such as $16, 4, 2, 10$ , holds no prime other than $2$ . The diagonal from the top left corner to the bottom right corner reads $17, 5, 1, 9, 25$ , and the other one reads $21, 7, 1, 3, 13$ , all odd.

Prime numbers

Definition A prime number is a whole number greater than $1$ whose only positive divisors are $1$ and itself. A whole number greater than $1$ that is not prime is composite, which means it is a product $a \times b$ of two whole numbers that are both greater than $1$ . The number $1$ is neither prime nor composite. Every whole number greater than $1$ is a prime or a product of primes, in only one way apart from the order of the factors, and there are infinitely many primes, as Euclid proved. To test whether a whole number $n > 1$ is prime, it is enough to try the primes up to $\sqrt{n}$ as divisors. If $n = a \times b$ with $1 < a \le b$ , then $a \le \sqrt{n}$ , and every prime factor of $a$ divides $n$ as well.

In plain words Primes are the whole numbers above $1$ that cannot be split into a product of two smaller whole numbers. Every other whole number above $1$ is built from them by multiplication.

Example The primes below $50$ are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43$ and $47$ , fifteen of them, and the gaps between neighbors, $1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4$ , change irregularly. To test $37$ , note that $\sqrt{37} \approx 6.08$ , so only $2$ , $3$ and $5$ need checking. The number $37$ is odd, its digit sum $10$ is not a multiple of $3$ , and it does not end in $0$ or $5$ , so $37$ is prime. The number $65$ ends in $5$ , and $65 = 5 \times 13$ is composite.

Quadratic polynomial

Definition A quadratic polynomial in a variable $k$ is an expression $ak^2 + bk + c$ with fixed numbers $a$ , $b$ and $c$ , where $a \ne 0$ . At $k = 0, 1, 2, \ldots$ the differences between consecutive values grow by the same amount $2a$ at every step, which makes a quadratic easy to recognize in a list of numbers. On the Ulam spiral, the number $k$ diagonal steps from $1$ in each of the four diagonal directions is

lower right, $(2k + 1)^2 = 4k^2 + 4k + 1$ ,
lower left, $4k^2 + 2k + 1$ ,
upper left, $4k^2 + 1$ ,
upper right, $4k^2 - 2k + 1$ ,

for every whole number $k \ge 0$ . More generally, far enough from the center the numbers along any diagonal line, read outward in one direction, are the values of a quadratic polynomial $4k^2 + bk + c$ with whole numbers $b$ and $c$ .

In plain words A quadratic polynomial is a formula whose highest power is a square. On the spiral the square comes from the square rings growing around the center, and the rest of the formula says how far around a ring the diagonal sits.

Example The ring at distance $k$ from the center is the border of a square of side $2k + 1$ . The numbers $1$ to $(2k + 1)^2$ fill that square, so the ring ends at its lower right corner with the number $(2k + 1)^2$ . Walking backward around the ring lowers the number by $1$ at each step. Going $2k$ steps back along the bottom reaches the lower left corner, $2k$ more up the left side reach the upper left corner, and $2k$ more along the top reach the upper right corner. So the upper left corner holds

\begin{aligned} &(2k + 1)^2 - 4k \\[0.4em] &\quad = 4k^2 + 4k + 1 - 4k \\[0.4em] &\quad = 4k^2 + 1, \end{aligned}

and the other corners follow in the same way. For $k = 1, 2, 3, 4$ the formulas give these numbers.

Diagonal	First four numbers	Formula
Lower right	$9, 25, 49, 81$	$(2k + 1)^2$
Lower left	$7, 21, 43, 73$	$4k^2 + 2k + 1$
Upper left	$5, 17, 37, 65$	$4k^2 + 1$
Upper right	$3, 13, 31, 57$	$4k^2 - 2k + 1$

On the upper left diagonal the differences are $12$ , $20$ and $28$ , growing by $8 = 2 \cdot 4$ each time, as a quadratic with $a = 4$ requires. The lower right diagonal stands out in the picture as a line with no prime at all, because each of its numbers after $1$ is the square of an odd number greater than $1$ and so has that odd number as a factor.

Prime-generating polynomial

Definition A polynomial with whole number coefficients is called prime-generating on a range of whole number inputs when all of its values on that range are prime. Every such run ends. No polynomial in one variable with whole number coefficients, other than a constant, has a prime value at every whole number input. The reason is divisibility. If $f(m) = p$ is prime, then $f(m + tp) - f(m)$ is a multiple of $p$ for every whole number $t$ , because each power $(m + tp)^j$ differs from $m^j$ by a multiple of $p$ . So $f(m + p)$ , $f(m + 2p)$ , $f(m + 3p)$ and so on are all multiples of $p$ . A polynomial that is not constant takes the value $p$ at only finitely many inputs, so one of these multiples is different from $p$ , and then it is not prime. The best-known example, studied by Leonhard Euler, is $n^2 + n + 41$ . It is prime for each of the forty inputs $n = 0, 1, \ldots, 39$ , while

\begin{aligned} 40^2 + 40 + 41 &= 1681 \\[0.4em] &= 41^2. \end{aligned}

A spiral that starts with $41$ in the center instead of $1$ , and follows the same path, puts the values $n^2 + n + 41$ for $n = 0, 1, 2, \ldots$ on the diagonal line through the center from lower left to upper right, alternately on its two sides. Its center, the next $20$ squares toward the upper right and the next $19$ toward the lower left all hold primes, and the $20$ th square toward the lower left holds $1681$ . No quadratic polynomial in one variable is known to take infinitely many prime values, not even $n^2 + 1$ .

In plain words A formula can give primes many times in a row and still fail at the next input. A long run of examples is evidence, not a proof.

Example The upper left diagonal, $4k^2 + 1$ , gives the primes $5$ , $17$ and $37$ and then $65 = 5 \times 13$ . Divisibility explains where the multiples of $5$ fall. When $k$ leaves remainder $1$ or $4$ on division by $5$ , the square $k^2$ leaves remainder $1$ , so $4k^2 + 1$ leaves remainder $4 + 1 = 5$ , which means that it is a multiple of $5$ . That happens at $k = 1, 4, 6, 9, 11, \ldots$ , with the values $5, 65, 145, 325, 485, \ldots$ , and only the first of them is $5$ itself. In the other direction, $4k^2 + 1$ is always odd, and since $k^2$ leaves remainder $0$ or $1$ on division by $3$ , it leaves remainder $1$ or $2$ , so it is never a multiple of $3$ . Among $k = 1$ to $100$ this diagonal holds $33$ primes, the upper right diagonal $32$ , the lower left $25$ and the lower right none. Whether the upper left diagonal holds infinitely many primes is not known. For $n > 1$ the number $n^2 + 1$ can only be prime when $n$ is even, and $n = 2k$ gives $4k^2 + 1$ , so the question is the same as whether $n^2 + 1$ is prime for infinitely many $n$ . Edmund Landau listed it in 1912 among four problems about primes, and it is still open.

Check yourself

Use the lower left formula $4k^2 + 2k + 1$ to find the numbers for $k = 1$ to $5$ . Check the first two against the grid of the first two rings, and decide which of the five numbers are prime.

Show the answer

The formula gives $7, 21, 43, 73$ and $111$ . The grid shows $7$ just below and to the left of $1$ , and $21$ in the lower left corner, as predicted. The number $7$ is prime and $21 = 3 \times 7$ is not. For $43$ , the primes up to $\sqrt{43} \approx 6.56$ are $2$ , $3$ and $5$ , and none of them divides $43$ , so it is prime. For $73$ , the primes up to $\sqrt{73} \approx 8.54$ are $2$ , $3$ , $5$ and $7$ , and none of them divides $73$ , so it is prime. Finally $111 = 3 \times 37$ . Three of the five numbers are prime.

Write $f(n) = n^2 + n + 17$ . It is prime for $n = 0, 1, \ldots, 15$ , and someone concludes that it is always prime. Find the first input where it fails, and explain why it must fail there without testing for primes. Which later inputs are sure to give multiples of $17$ ?

Show the answer

At $n = 16$ the value is $16^2 + 16 + 17 = 289 = 17^2$ . The failure is built in, because $n^2 + n = n(n + 1)$ , which at $n = 16$ is $16 \times 17$ , so the value is $16 \times 17 + 17 = 17 \times 17$ . More generally $f(n) = n(n + 1) + 17$ , and since $17$ is prime, $f(n)$ is a multiple of $17$ exactly when $n$ or $n + 1$ is. That happens at $n = 16, 17, 33, 34, 50, 51$ and so on, for example $f(17) = 323 = 17 \times 19$ and $f(34) = 1207 = 17 \times 71$ . All of these values are larger than $17$ , so none of them is prime. This matches the argument in the definition, which starts from $f(0) = 17$ and finds the multiples $f(17)$ , $f(34)$ , $f(51)$ and so on. Sixteen primes in a row were evidence, but the polynomial could never give primes forever. The polynomial $n^2 + n + 41$ fails at $n = 40$ for the same reason, since $40 \times 41 + 41 = 41^2$ .

Show that $3$ never divides $4k^2 + 1$ , and that $3$ divides $4k^2 + 2k + 1$ exactly when $k$ leaves remainder $2$ on division by $3$ . What does this say about the lower left diagonal?

Show the answer

A whole number $k$ leaves remainder $0$ , $1$ or $2$ on division by $3$ , and then $k^2$ leaves remainder $0$ , $1$ or $1$ , since $2^2 = 4$ leaves remainder $1$ . Because $4$ leaves remainder $1$ , the number $4k^2 + 1$ leaves the same remainder as $k^2 + 1$ , which is $1$ or $2$ and never $0$ . In the same way $4k^2 + 2k + 1$ leaves the same remainder as $k^2 + 2k + 1 = (k + 1)^2$ . Since $3$ is prime, this square is a multiple of $3$ exactly when $k + 1$ is, that is, when $k$ leaves remainder $2$ .

So on the lower left diagonal the squares at $k = 2, 5, 8, \ldots$ hold multiples of $3$ , such as $21$ , $111$ and $273$ , and since these are larger than $3$ they are composite. One square in three on that diagonal is ruled out by $3$ alone, while the upper left diagonal never loses a square to $3$ . That fits the counts of $25$ and $33$ primes among the first $100$ squares of these two diagonals. The upper right formula $4k^2 - 2k + 1$ leaves the remainder of $(k - 1)^2$ , so that diagonal loses the squares where $k$ leaves remainder $1$ , starting with $57 = 3 \times 19$ at $k = 4$ , after the prime $3$ itself at $k = 1$ .