Ulam spiral

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.^[1] 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 x² − x + 41, are believed to produce a high density of prime numbers.^[2][3] 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.^[4]

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 201×201 Ulam spiral shown above, diagonal lines are clearly visible, confirming the pattern to that point. 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.^[5]

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.^[1] 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.^[6] 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.^[7][8] 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."^[4]

Diagonal, horizontal, and vertical lines in the number spiral correspond to polynomials of the form

${\displaystyle f(n)=4n^{2}+bn+c}$

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 ${\displaystyle 4n^{2}+8n+3}$, while producing only odd values, factorize over the integers ${\displaystyle (4n^{2}+8n+3)=(2n+1)(2n+3)}$ 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.

To gain insight into why some of the remaining odd diagonals may have a higher concentration of primes than others, consider ${\displaystyle 4n^{2}+6n+1}$ and ${\displaystyle 4n^{2}+6n+5}$. Compute remainders upon division by 3 as n takes successive values 0, 1, 2, .... For the first of these polynomials, the sequence of remainders is 1, 2, 2, 1, 2, 2, ..., while for the second, it is 2, 0, 0, 2, 0, 0, .... This implies that in the sequence of values taken by the second polynomial, two out of every three are divisible by 3, and hence certainly not prime, while in the sequence of values taken by the first polynomial, none are divisible by 3. Thus it seems plausible that the first polynomial will produce values with a higher density of primes than will the second. At the very least, this observation gives little reason to believe that the corresponding diagonals will be equally dense with primes. One should, of course, consider divisibility by primes other than 3. Examining divisibility by 5 as well, remainders upon division by 15 repeat with pattern 1, 11, 14, 10, 14, 11, 1, 14, 5, 4, 11, 11, 4, 5, 14 for the first polynomial, and with pattern 5, 0, 3, 14, 3, 0, 5, 3, 9, 8, 0, 0, 8, 9, 3 for the second, implying that only three out of 15 values in the second sequence are potentially prime (being divisible by neither 3 nor 5), while 12 out of 15 values in the first sequence are potentially prime (since only three are divisible by 5 and none are divisible by 3).

While rigorously-proved results about primes in quadratic sequences are scarce, considerations like those above give rise to a plausible conjecture on the asymptotic density of primes in such sequences, which is described in the next section.

In their 1923 paper on the Goldbach Conjecture, Hardy and Littlewood stated a series of conjectures, one of which, if true, would explain some of the striking features of the Ulam spiral. This conjecture, which Hardy and Littlewood called "Conjecture F", is a special case of the Bateman–Horn conjecture and asserts an asymptotic formula for the number of primes of the form ax² + bx + c. Rays emanating from the central region of the Ulam spiral making angles of 45° with the horizontal and vertical correspond to numbers of the form 4x² + bx + c with b even; horizontal and vertical rays correspond to numbers of the same form with b odd. Conjecture F provides a formula that can be used to estimate the density of primes along such rays. It implies that there will be considerable variability in the density along different rays. In particular, the density is highly sensitive to the discriminant of the polynomial, b² − 16c.

Conjecture F is concerned with polynomials of the form ax² + bx + c where a, b, and c are integers and a is positive. If the coefficients contain a common factor greater than 1 or if the discriminant Δ = b² − 4ac is a perfect square, the polynomial factorizes and therefore produces composite numbers as x takes the values 0, 1, 2, ... (except possibly for one or two values of x where one of the factors equals 1). Moreover, if a + b and c are both even, the polynomial produces only even values, and is therefore composite except possibly for the value 2. Hardy and Littlewood assert that, apart from these situations, ax² + bx + c takes prime values infinitely often as x takes the values 0, 1, 2, ... This statement is a special case of an earlier conjecture of Bunyakovsky and remains open. Hardy and Littlewood further assert that, asymptotically, the number P(n) of primes of the form ax² + bx + c and less than n is given by

${\displaystyle P(n)\sim A{\frac {1}{\sqrt {a}}}{\frac {\sqrt {n}}{\log n}}}$

where A depends on a, b, and c but not on n. By the prime number theorem, this formula with A set equal to one is the asymptotic number of primes less than n expected in a random set of numbers having the same density as the set of numbers of the form ax² + bx + c. But since A can take values bigger or smaller than 1, some polynomials, according to the conjecture, will be especially rich in primes, and others especially poor. An unusually rich polynomial is 4x² − 2x + 41 which forms a visible line in the Ulam spiral. The constant A for this polynomial is approximately 6.6, meaning that the numbers it generates are almost seven times as likely to be prime as random numbers of comparable size, according to the conjecture. This particular polynomial is related to Euler's prime-generating polynomial x² − x + 41 by replacing x with 2x, or equivalently, by restricting x to the even numbers. The constant A is given by a product running over all prime numbers,

${\displaystyle A=\prod \limits _{p}{\frac {p-\omega (p)}{p-1}}~}$,

in which ${\displaystyle \omega (p)}$ is number of zeros of the quadratic polynomial modulo p and therefore takes one of the values 0, 1, or 2. Hardy and Littlewood break the product into three factors as

${\displaystyle A=\varepsilon \prod _{p}{\biggl (}{\frac {p}{p-1}}{\biggr )}\,\prod _{\varpi }{\biggl (}1-{\frac {1}{\varpi -1}}{\Bigl (}{\frac {\Delta }{\varpi }}{\Bigr )}{\biggr )}}$.

Here the factor ε, corresponding to the prime 2, is 1 if a + b is odd and 2 if a + b is even. The first product index p runs over the finitely-many odd primes dividing both a and b. For these primes ${\displaystyle \omega (p)=0}$ since p then cannot divide c. The second product index ${\displaystyle \varpi }$ runs over the infinitely-many odd primes not dividing a. For these primes ${\displaystyle \omega (p)}$ equals 1, 2, or 0 depending on whether the discriminant is 0, a non-zero square, or a non-square modulo p. This is accounted for by the use of the Legendre symbol, ${\displaystyle \left({\frac {\Delta }{\varpi }}\right)}$. When a prime p divides a but not b there is one root modulo p. Consequently, such primes do not contribute to the product.

A quadratic polynomial with A ≈ 11.3, currently the highest known value, has been discovered by Jacobson and Williams.^[9][10]

Klauber's 1932 paper describes a triangle in which row n contains the numbers (n  −  1)² + 1 through n². As in the Ulam spiral, quadratic polynomials generate numbers that lie in straight lines. Vertical lines correspond to numbers of the form k² − k + M. Vertical and diagonal lines with a high density of prime numbers are evident in the figure.

Robert Sacks devised a variant of the Ulam spiral in 1994. In the Sacks spiral, the non-negative integers are plotted on an Archimedean spiral rather than the square spiral used by Ulam, and are spaced so that one perfect square occurs in each full rotation. (In the Ulam spiral, two squares occur in each rotation.) Euler's prime-generating polynomial, x² − x + 41, now appears as a single curve as x takes the values 0, 1, 2, ... This curve asymptotically approaches a horizontal line in the left half of the figure. (In the Ulam spiral, Euler's polynomial forms two diagonal lines, one in the top half of the figure, corresponding to even values of x in the sequence, the other in the bottom half of the figure corresponding to odd values of x in the sequence.)

Additional structure may be seen when composite numbers are also included in the Ulam spiral. The number 1 has only a single factor, itself; each prime number has two factors, itself and 1; composite numbers are divisible by at least three different factors. Using the size of the dot representing an integer to indicate the number of factors and coloring prime numbers red and composite numbers blue produces the figure shown.

Spirals following other tilings of the plane also generate lines rich in prime numbers, for example hexagonal spirals.

• 
  Klauber triangle with prime numbers generated by Euler's polynomial x²  −  x  +  41 highlighted.
• 
  Sacks spiral.
• 
  Ulam spiral of size 150×150 showing both prime and composite numbers.
• 
  Hexagonal number spiral with prime numbers in green and more highly composite numbers in darker shades of blue.
• 
  Number spiral with 7503 primes visible on regular triangle.
• 
  Ulam spiral with 10 million primes.

• Pattern recognition
• Prime k-tuple

Wikimedia Commons has media related to Ulam spiral.