Ulam spiral

Last updated
Ulam spiral of size 200x200. Black dots represent prime numbers. Diagonal, vertical, and horizontal lines with a high density of prime numbers are clearly visible. Ulam 1.png
Ulam spiral of size 200×200. Black dots represent prime numbers. Diagonal, vertical, and horizontal lines with a high density of prime numbers are clearly visible.
For comparison, a spiral with random odd numbers colored black (at the same density of primes in a 200x200 spiral). Randomly black odd numbers.png
For comparison, a spiral with random odd numbers colored black (at the same density of primes in a 200x200 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.

Contents

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. [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, more than thirty 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]

Construction

The Ulam spiral is constructed by writing the positive integers in a spiral arrangement on a square lattice:

Numbers from 1 to 49 placed in spiral order Ulam spiral howto all numbers.svg
Numbers from 1 to 49 placed in spiral order

and then marking the prime numbers:

Small Ulam spiral Ulam spiral howto primes only.svg
Small Ulam spiral

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. [5]

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. [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]

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.

To gain insight into why some of the remaining odd diagonals may have a higher concentration of primes than others, consider and . 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 and asserts an asymptotic formula for the number of primes of the form ax2 + 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 4x2 + 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, b2 − 16c.

The primes of the form 4x  - 2x + 41 with x = 0, 1, 2, ... have been highlighted in purple. The prominent parallel line in the lower half of the figure corresponds to 4x  + 2x + 41 or, equivalently, to negative values of x. Ulam 2.png
The primes of the form 4x  − 2x + 41 with x = 0, 1, 2, ... have been highlighted in purple. The prominent parallel line in the lower half of the figure corresponds to 4x  + 2x + 41 or, equivalently, to negative values of x.

Conjecture F is concerned with polynomials of the form ax2 + 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 Δ = b2 − 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, ax2 + 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 ax2 + bx + c and less than n is given by

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 ax2 + 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 4x2 − 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 x2 − 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,

,

in which 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

.

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 since p then cannot divide c. The second product index runs over the infinitely-many odd primes not dividing a. For these primes 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, . 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]

Variants

Klauber's 1932 paper describes a triangle in which row n contains the numbers (n  −  1)2 + 1 through n2. As in the Ulam spiral, quadratic polynomials generate numbers that lie in straight lines. Vertical lines correspond to numbers of the form k2 − 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, x2 − 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.

See also

Related Research Articles

Modular arithmetic Computation modulo a fixed integer

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

Number theory Branch of mathematics

Number theory is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen of mathematics." Number theorists study prime numbers as well as the properties of mathematical objects made out of integers or defined as generalizations of the integers.

Prime number Positive integer with exactly two divisors, 1 and itself

A prime number 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 of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

In mathematics, a transcendental number is a number that is not algebraic—that is, not the root of a non-zero polynomial of finite degree with rational coefficients. The best known transcendental numbers are π and e.

Goldbachs conjecture Conjecture that every even integer greater than 2 is the sum of two primes

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states that every even whole number greater than 2 is the sum of two prime numbers.

In number theory, Dirichlet's theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n is also a positive integer. In other words, there are infinitely many primes that are congruent to a modulo d. The numbers of the form a + nd form an arithmetic progression

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.

Analytic number theory Exploring properties of the integers with complex analysis

In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic progressions. It is well known for its results on prime numbers and additive number theory.

In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. No such formula which is efficiently computable is known. A number of constraints are known, showing what such a "formula" can and cannot be.

In mathematics, Schinzel's hypothesis H is one of the most famous open problems in the topic of number theory. It is a very broad generalisation of widely open conjectures such as the twin prime conjecture. The hypothesis is named after Andrzej Schinzel.

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 a vast generalization of such conjectures as the Hardy and Littlewood conjecture on the density of twin primes or their conjecture on primes of the form n2 + 1; it is also a strengthening of Schinzel's hypothesis H.

In mathematics, an Euler brick, named after Leonhard Euler, is a rectangular cuboid whose edges and face diagonals all have integer lengths. A primitive Euler brick is an Euler brick whose edge lengths are relatively prime. A perfect Euler brick is one where the longest space diagonal is also an integer but such a brick has not yet been found.

Euclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. It was first proved by Euclid in his work Elements. There are several proofs of the theorem.

Kempner function

In number theory, the Kempner functionS(n) is defined for a given positive integer n to be the smallest number s such that n divides the factorial s!. For example, the number 8 does not divide 1!, 2!, 3!, but does divide 4!, so S(8) = 4.

The Bunyakovsky conjecture gives a criterion for a polynomial in one variable with integer coefficients to give infinitely many prime values in the sequence It was stated in 1857 by the Russian mathematician Viktor Bunyakovsky. The following three conditions are necessary for to have the desired prime-producing property:

  1. The leading coefficient is positive,
  2. The polynomial is irreducible over the integers.
  3. The values have no common factor.

Euler's "lucky" numbers are positive integers n such that for all integers k with 1 ≤ k < n, the polynomial k2k + n produces a prime number.

In mathematics, a Størmer number or arc-cotangent irreducible number, named after Carl Størmer, is a positive integer n for which the greatest prime factor of n2 + 1 is greater than or equal to 2n.

In mathematics, Carmichael's totient function conjecture concerns the multiplicity of values of Euler's totient function φ(n), which counts the number of integers less than and coprime to n. It states that, for every n there is at least one other integer m ≠ n such that φ(m) = φ(n). Robert Carmichael first stated this conjecture in 1907, but as a theorem rather than as a conjecture. However, his proof was faulty, and in 1922, he retracted his claim and stated the conjecture as an open problem.

In mathematics, specifically the area of algebraic number theory, a cubic field is an algebraic number field of degree three.

References

  1. 1 2 Gardner 1964, p. 122.
  2. Stein, Ulam & Wells 1964, p. 517.
  3. Gardner 1964, p. 124.
  4. 1 2 Daus 1932, p. 373.
  5. Mollin 1996, p. 21.
  6. Stein, Ulam & Wells 1964, p. 520.
  7. Gardner 1971, p. 88.
  8. Hartwig, Daniel (2013), Guide to the Martin Gardner papers, The Online Archive of California, p. 117.
  9. Jacobson Jr., M. J.; Williams, H. C (2003), "New quadratic polynomials with high densities of prime values" (PDF), Mathematics of Computation , 72 (241): 499–519, Bibcode:2003MaCom..72..499J, doi: 10.1090/S0025-5718-02-01418-7
  10. Guy, Richard K. (2004), Unsolved problems in number theory (3rd ed.), Springer, p. 8, ISBN   978-0-387-20860-2

Bibliography