View source for Kin selection

[[Image:Ulam 1.png|right|thumb|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.]]
The '''Ulam spiral''', or '''prime spiral''' (in other languages also called the '''Ulam Cloth''') is a simple method of visualizing the [[prime number]]s that reveals the apparent tendency of certain quadratic polynomials to generate unusually large numbers of primes. It was discovered by the [[mathematician]] [[Stanislaw Ulam]] in 1963, while he was [[Doodle|doodling]] during the presentation of a “long and very boring paper”{{sfn|Gardner|1964|p=122}} at a scientific meeting.  Shortly afterwards, in an early application of computer graphics, Ulam with collaborators Myron Stein and Mark Wells used [[MANIAC II]] at [[Los Alamos National Laboratory|Los Alamos Scientific Laboratory]] to produce pictures of the spiral for numbers up to 65,000.{{sfn|Stein|Ulam|Wells|1964|p=520}}{{sfn|Gardner|1964|p=122}}{{sfn|Hoffman|1988|p=41}}  In March of the following year, [[Martin Gardner]] wrote about the Ulam spiral in his ''[[Recreational mathematics|Mathematical Games]]'' column;{{sfn|Gardner|1964|p=122}} the Ulam spiral featured on the front cover of the issue of ''[[Scientific American]]'' in which the column appeared.

In an addendum to the ''Scientific American'' column,{{sfn|Gardner|1971|p=88}} Gardner mentions work of the [[herpetologist]] [[Laurence Monroe Klauber|Laurence M. Klauber]] on two dimensional arrays of prime numbers for finding prime-rich quadratic polynomials which was presented at a meeting of the [[Mathematical Association of America]] in 1932—more than thirty years prior to Ulam's discovery.  Unlike Ulam's array, Klauber's was not a spiral.  Its shape was also triangular rather than square.<ref>{{citation
 | title = Guide to the Martin Gardner papers
 | author = Daniel Hartwig
 | publisher = The Online Archive of California
 | year = 2013
 | page = 117
 | url = http://www.oac.cdlib.org/findaid/ark:/13030/kt6s20356s/
}}.</ref>

==Construction==
Ulam constructed the spiral by writing down a regular [[rectangle|rectangular]] [[Lattice graph|grid]] of numbers, starting with 1 at the center, and [[spiral]]ing out:

[[Image:Ulam spiral howto all numbers.svg|200px|center|Numbers from 1 to 49 placed in spiral order]]

He then circled all of the prime numbers and he got the following picture:

[[Image:Ulam spiral howto primes only.svg|200px|center|Small Ulam spiral]]

To his surprise, the circled numbers tended to line up along [[diagonal]] lines.  In the 200×200 Ulam spiral shown above, diagonal lines are clearly visible, confirming the pattern.  Horizontal and vertical lines, while less prominent, are also evident.

All prime numbers, except for the number 2, are odd numbers. Since in the Ulam spiral adjacent diagonals are alternatively odd and even numbers, it is no surprise that all prime numbers lie in alternate diagonals of the Ulam spiral. What is startling is the tendency of prime numbers to lie on some diagonals more than others.

Tests so far confirm that there are diagonal lines even when [[:File:Ulam4004001.png|many numbers are plotted]]. The pattern also seems to appear even if the number at the center is not 1 (and can, in fact, be much larger than 1). This implies that there are many integer constants ''b'' and ''c'' such that the [[Function (mathematics)|function]]:

: <math>f(n) = 4 n^2 + b n + c</math>

generates, as ''n'' counts up {1, 2, 3, ...}, a number of primes that is large by comparison with the proportion of primes among numbers of similar magnitude.

==Hardy and Littlewood's Conjecture F==
In their 1923 paper on the [[Goldbach's conjecture|Goldbach Conjecture]], [[G. H. Hardy|Hardy]] and [[John Edensor Littlewood|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''<sup>2</sup> + ''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''<sup>2</sup> + ''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''<sup>2</sup> − 16''c''.

[[Image:Ulam 2.png|250px|right|thumb|The primes of the form 4''x''<sup>2</sup> − 2''x'' + 41 with ''x'' = 0, 1, 2, ... have been highlighted. The prominent parallel line in the lower half of the figure corresponds to 4''x''<sup>2</sup> + 2''x'' + 41 or, equivalently, to negative values of ''x''.]]
Conjecture F is concerned with polynomials of the form ''ax''<sup>2</sup> + ''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''<sup>2</sup> − 4''ac'' is a [[square number|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''<sup>2</sup> + ''bx'' + ''c'' takes prime values infinitely often as ''x'' takes the values 0, 1, 2, ...  This statement is a special case of an earlier [[Bunyakovsky conjecture|conjecture of Bunyakovsky]] and remains open.  Hardy and Littlewood further assert that, asymptotically, the number ''P''(''n'') of primes of the form ''ax''<sup>2</sup> + ''bx'' + ''c'' and less than ''n'' is given by

: <math>P(n)\sim A\frac{1}{\sqrt{a}}\frac{\sqrt{n}}{\log n}</math>

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''<sup>2</sup> + ''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''<sup>2</sup> − 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 [[Formula for primes#Prime formulas and polynomial functions|prime-generating polynomial]] ''x''<sup>2</sup> − ''x'' + 41 by replacing ''x'' with 2''x'', or equivalently, by restricting ''x'' to the even numbers.  Hardy and Littlewood's formula for the constant ''A'' is

: <math>A=\varepsilon\prod_p\left(\frac{p}{p-1}\right)\prod_{\varpi}\left(1-\frac{1}{\varpi-1}\left(\frac{\Delta}{\varpi}\right)\right).</math>

In the first product, ''p'' is a prime dividing both ''a'' and ''b''; in the second product, <math>\varpi</math> is an odd prime not dividing ''a''.  The quantity ε is defined to be 1 if ''a'' + ''b'' is odd and 2 if ''a'' + ''b'' is even.  The symbol <math>\left(\frac{\Delta}{\varpi}\right)</math> is the [[Legendre symbol]].  A quadratic polynomial with ''A'' ≈ 11.3, currently the highest known value, has been discovered by Jacobson and Williams.<ref>{{citation|last1=Jacobson Jr.|first1=M. J.|last2=Williams|first2=H. C|title=New quadratic polynomials with high densities of prime values|year=2003|journal=[[Mathematics of Computation]]|volume=72|pages=499–519|doi=10.1090/S0025-5718-02-01418-7|issue=241}}</ref><ref>{{Citation |author=Guy, Richard K. |url=http://books.google.com/?id=1AP2CEGxTkgC&printsec=frontcover |title=Unsolved problems in number theory |publisher=Springer |edition=3rd|year=2004 |isbn=978-0-387-20860-2|page=8}}</ref>

==Variants==
[[File:KlauberTriangle.png|thumb|Klauber triangle with prime numbers generated by Euler's polynomial ''x''<sup>2</sup>  −  ''x''  +  41 highlighted.]]
Klauber's 1932 paper describes a triangle in which row ''n'' contains the numbers (''n''  −  1)<sup>2</sup> + 1 through ''n''<sup>2</sup>.  As in the Ulam spiral, quadratic polynomials generate numbers that lie in straight lines.  Vertical lines correspond to numbers of the form ''k''<sup>2</sup> − ''k'' + ''M''.  Vertical and diagonal lines with a high density of prime numbers are evident in the figure.

[[Image:Sacks spiral.svg|150px|left|thumb|Sacks spiral]]
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 [[square number|perfect square]] occurs in each full rotation.  (In the Ulam spiral, two squares occur in each rotation.)  Euler's prime-generating polynomial, ''x''<sup>2</sup> − ''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.)
<!-- [http://www.numberspiral.com Robert Sacks' web site] Don't download software: contains four trojan horses. -->
<!-- Might be nice to include above as citation, if trojan horse issue is resolved. -->

[[File:Spirale Ulam 150.jpg|150px|right|thumb|Ulam spiral of size 150×150 showing both prime and composite numbers.]]
Additional structure may be seen when [[composite number]]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.

== Notes ==
{{reflist}}

== References ==
{{refbegin}}
*{{citation
 | last = Gardner | first = M. | author-link = Martin Gardner
 |date=March 1964
 | journal = [[Scientific American]]
 | pages = 120–128
 | title = Mathematical Games: The Remarkable Lore of the Prime Number
 | volume = 210
 | doi = 10.1038/scientificamerican0364-120
}}.
*{{citation
 | last = Gardner | first = M. | author-link = Martin Gardner
 | publisher = University of Chicago Press
 | date = 1971
 | title = Martin Gardner's Sixth Book of Mathematical Diversions from Scientific American
 | isbn = 978-0-226-28250-3
}}.
*{{citation
 | last1 = Hardy | first1 = G. H.
 | last2 = Littlewood | first2 = J. E.
 | journal = [[Acta Mathematica]]
 | pages = 1–70
 | title = Some Problems of 'Partitio Numerorum'; III: On the Expression of a Number as a Sum of Primes
 | volume = 44
 | year = 1923
 | doi=10.1007/BF02403921
}} {{closed access}}.
*{{citation
 | last=Hoffman | first=Paul | author-link = Paul Hoffman (science writer)
 | title=Archimedes' Revenge: The Joys and Perils of Mathematics
 | publisher=Fawcett Colombine
 | location=New York
 | year=1988
 | isbn=0-449-00089-3}}.
*{{citation
 | last1 = Stein | first1 = M. L.
 | last2 = Ulam | first2 = S. M.
 | last3 = Wells | first3 = M. B.
 | journal = [[American Mathematical Monthly]]
 | pages = 516–520
 | title = A Visual Display of Some Properties of the Distribution of Primes
 | jstor = 2312588
 | volume = 71
 | year = 1964
 | doi = 10.2307/2312588
 | issue = 5
 | publisher = Mathematical Association of America
}}.
*{{citation
 | last1 = Stein | first1 = M.
 | last2 = Ulam | first2 = S. M.
 | journal = American Mathematical Monthly
 | pages = 43–44
 | title = An Observation on the Distribution of Primes
 | jstor = 2314055
 | volume = 74
 | year = 1967
 | doi = 10.2307/2314055
 | issue = 1
 | publisher = Mathematical Association of America
}}.
{{refend}}

==External links==
*[http://www.youtube.com/watch?v=iFuR97YcSLM Prime Spirals - Numberphile], YouTube video with Dr. James Grime and the [[University of Nottingham]]
*[http://www.youtube.com/watch?v=3K-12i0jclM 41 and more Ulam's Spiral - Numberphile], YouTube video with Dr. James Clewett and the University of Nottingham

[[Category:Prime numbers]]
[[Category:Spirals]]