HOME

TheInfoList



OR:

The Ulam spiral or prime spiral is a graphical depiction of the set of
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s, devised by mathematician
Stanisław Ulam Stanisław Marcin Ulam (; 13 April 1909 – 13 May 1984) was a Polish-American scientist in the fields of mathematics and nuclear physics. He participated in the Manhattan Project, originated the Teller–Ulam design of thermonuclear weapon ...
in 1963 and popularized in Martin Gardner's ''
Mathematical Games A mathematical game is a game whose rules, strategies, and outcomes are defined by clear mathematical parameters. Often, such games have simple rules and match procedures, such as Tic-tac-toe and Dots and Boxes. Generally, mathematical games ne ...
'' column in ''
Scientific American ''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many famous scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it. In print since 1845, it i ...
'' 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 Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
's prime-generating polynomial ''x''2 − ''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 Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777 ...
such as
Landau's problems At the 1912 International Congress of Mathematicians, Edmund Landau listed four basic problems about prime numbers. These problems were characterised in his speech as "unattackable at the present state of mathematics" and are now known as Landau ...
. 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 In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 19 ...
as to what that asymptotic density should be. In 1932, 31 years prior to Ulam's discovery, the
herpetologist Herpetology (from Greek ἑρπετόν ''herpetón'', meaning "reptile" or "creeping animal") is the branch of zoology concerned with the study of amphibians (including frogs, toads, salamanders, newts, and caecilians (gymnophiona)) and rept ...
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 In mathematics, a spiral is a curve which emanates from a point, moving farther away as it revolves around the point. Helices Two major definitions of "spiral" in the American Heritage Dictionary are:square lattice In mathematics, the square lattice is a type of lattice in a two-dimensional Euclidean space. It is the two-dimensional version of the integer lattice, denoted as . It is one of the five types of two-dimensional lattices as classified by their ...
: : 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 The MANIAC II (''Mathematical Analyzer Numerical Integrator and Automatic Computer Model II'') was a first-generation electronic computer, built in 1957 for use at Los Alamos Scientific Laboratory. MANIAC II was built by the University of Califor ...
at
Los Alamos Scientific Laboratory Los Alamos National Laboratory (often shortened as Los Alamos and LANL) is one of the sixteen research and development laboratories of the United States Department of Energy (DOE), located a short distance northwest of Santa Fe, New Mexico, in ...
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 : f(n) = 4 n^2 + b n + 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 4 n^2 + 8 n + 3, while producing only odd values, factorize over the integers (4 n^2 + 8 n + 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 4 n^2 + 6 n + 1 and 4 n^2 + 6 n + 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.


Hardy and Littlewood's Conjecture F

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 In number theory, the Bateman–Horn conjecture is a statement concerning the frequency of prime numbers among the values of a system of polynomials, named after mathematicians Paul T. Bateman and Roger A. Horn who proposed it in 1962. It provides ...
and asserts an asymptotic formula for the number of primes of the form ''ax''2 + ''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 4''x''2 + ''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 In mathematics, the discriminant of a polynomial is a quantity that depends on the coefficients and allows deducing some properties of the roots without computing them. More precisely, it is a polynomial function of the coefficients of the origi ...
of the polynomial, ''b''2 − 16''c''. Conjecture F is concerned with polynomials of the form ''ax''2 + ''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''2 − 4''ac'' is a perfect square, the polynomial factorizes and therefore produces
composite numbers A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
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''2 + ''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''2 + ''bx'' + ''c'' and less than ''n'' is given by : P(n)\sim A\frac\frac where ''A'' depends on ''a'', ''b'', and ''c'' but not on ''n''. By the
prime number theorem In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying ...
, 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''2 + ''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 4''x''2 − 2''x'' + 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''2 − ''x'' + 41 by replacing ''x'' with 2''x'', or equivalently, by restricting ''x'' to the even numbers. The constant ''A'' is given by a product running over all prime numbers, : A = \prod\limits_ \frac~, in which \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 : A = \varepsilon\prod_p \biggl(\frac\biggr)\,\prod_\biggl(1-\frac\Bigl(\frac\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 \omega (p)=0 since ''p'' then cannot divide ''c''. The second product index \varpi runs over the infinitely-many odd primes not dividing ''a''. For these primes \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 In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number ''p'': its value at a (nonzero) quadratic residue mod ''p'' is 1 and at a non-quadratic residu ...
, \left(\frac\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.


Variants

Klauber's 1932 paper describes a triangle in which row ''n'' contains the numbers (''n''  −  1)2 + 1 through ''n''2. As in the Ulam spiral, quadratic polynomials generate numbers that lie in straight lines. Vertical lines correspond to numbers of the form ''k''2 − ''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 The Archimedean spiral (also known as the arithmetic spiral) is a spiral named after the 3rd-century BC Greek mathematician Archimedes. It is the locus corresponding to the locations over time of a point moving away from a fixed point with a con ...
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''2 − ''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 number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
s 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. File:KlauberTriangle.png, Klauber triangle with prime numbers generated by Euler's polynomial ''x''2  −  ''x''  +  41 highlighted. Image:Sacks spiral.svg, Sacks spiral. File:Spirale Ulam 150.jpg, Ulam spiral of size 150×150 showing both prime and composite numbers. File:Hexgrid prime number spiral.svg, Hexagonal number spiral with prime numbers in green and more highly composite numbers in darker shades of blue. File:Ulamtriangle.png, Number spiral with 7503 primes visible on regular triangle.


See also

*
Pattern recognition Pattern recognition is the automated recognition of patterns and regularities in data. It has applications in statistical data analysis, signal processing, image analysis, information retrieval, bioinformatics, data compression, computer graphi ...
*
Prime k-tuple In number theory, a prime -tuple is a finite collection of values representing a repeatable pattern of differences between prime numbers. For a -tuple , the positions where the -tuple matches a pattern in the prime numbers are given by the set o ...


References


Bibliography

* * * * * * * * * {{Commons category, Ulam spiral Prime numbers Spirals