The Ulam spiral or prime spiral is a graphical depiction of the set of prime numbers, devised by mathematician Stanisław Ulam in 1963 and popularized in Martin Gardner's Mathematical Games column in Scientific American a short time later. It is constructed by writing the positive integers in a square spiral and specially marking the prime numbers.
Ulam and Gardner emphasized the striking appearance in the spiral of prominent diagonal, horizontal, and vertical lines containing large numbers of primes. Both Ulam and Gardner noted that the existence of such prominent lines is not unexpected, as lines in the spiral correspond to quadratic polynomials, and certain such polynomials, such as Euler's prime-generating polynomial x2 − x + 41, are believed to produce a high density of prime numbers. Nevertheless, the Ulam spiral is connected with major unsolved problems in number theory such as Landau's problems. In particular, no quadratic polynomial has ever been proved to generate infinitely many primes, much less to have a high asymptotic density of them, although there is a well-supported conjecture as to what that asymptotic density should be.
In 1932, 31 years prior to Ulam's discovery, the herpetologist Laurence Klauber constructed a triangular, non-spiral array containing vertical and diagonal lines exhibiting a similar concentration of prime numbers. Like Ulam, Klauber noted the connection with prime-generating polynomials, such as Euler's.
Construction
The Ulam spiral is constructed by writing the positive integers in a spiral arrangement on a square lattice:
and then marking the prime numbers:
In the figure, primes appear to concentrate along certain diagonal lines. In the 200×200 Ulam spiral shown above, diagonal lines are clearly visible, confirming that the pattern continues. Horizontal and vertical lines with a high density of primes, while less prominent, are also evident. Most often, the number spiral is started with the number 1 at the center, but it is possible to start with any number, and the same concentration of primes along diagonal, horizontal, and vertical lines is observed. Starting with 41 at the center gives a diagonal containing an unbroken string of 40 primes (starting from 1523 southwest of the origin, decreasing to 41 at the origin, and increasing to 1601 northeast of the origin), the longest example of its kind.
History
According to Gardner, Ulam discovered the spiral in 1963 while doodling during the presentation of "a long and very boring paper" at a scientific meeting. These hand calculations amounted to "a few hundred points". Shortly afterwards, Ulam, with collaborators Myron Stein and Mark Wells, used MANIAC II at Los Alamos Scientific Laboratory to extend the calculation to about 100,000 points. The group also computed the density of primes among numbers up to 10,000,000 along some of the prime-rich lines as well as along some of the prime-poor lines. Images of the spiral up to 65,000 points were displayed on "a scope attached to the machine" and then photographed. The Ulam spiral was described in Martin Gardner's March 1964 Mathematical Games column in Scientific American and featured on the front cover of that issue. Some of the photographs of Stein, Ulam, and Wells were reproduced in the column.
In an addendum to the Scientific American column, Gardner mentioned the earlier paper of Klauber. Klauber describes his construction as follows, "The integers are arranged in triangular order with 1 at the apex, the second line containing numbers 2 to 4, the third 5 to 9, and so forth. When the primes have been indicated, it is found that there are concentrations in certain vertical and diagonal lines, and amongst these the so-called Euler sequences with high concentrations of primes are discovered."
Explanation
Diagonal, horizontal, and vertical lines in the number spiral correspond to polynomials of the form
where b and c are integer constants. When b is even, the lines are diagonal, and either all numbers are odd, or all are even, depending on the value of c. It is therefore no surprise that all primes other than 2 lie in alternate diagonals of the Ulam spiral. Some polynomials, such as , while producing only odd values, factorize over the integers and are therefore never prime except possibly when one of the factors equals 1. Such examples correspond to diagonals that are devoid of primes or nearly so.