Editing Ulam spiral (section)

==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|thumb|The primes of the form 4''x''<sup>2</sup> − 2''x'' + 41 with ''x'' = 0, 1, 2, ... have been highlighted in purple. 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. The constant ''A'' is given by a product running over all prime numbers,

: <math> A = \prod\limits_{p} \frac{p-\omega(p)}{p-1}~</math>,

in which <math>\omega (p)</math> is number of zeros of the quadratic polynomial [[modular arithmetic|modulo]] ''p'' and therefore takes one of the values 0, 1, or 2.  Hardy and Littlewood break the product into three factors as

: <math>A = \varepsilon\prod_p \biggl(\frac{p}{p-1}\biggr)\,\prod_{\varpi}\biggl(1-\frac{1}{\varpi-1}\Bigl(\frac{\Delta}{\varpi}\Bigr)\biggr)</math>.

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 <math>\omega (p)=0</math> since  ''p'' then cannot divide ''c''. The second product index <math>\varpi</math> runs over the infinitely-many odd primes not dividing ''a''. For these primes <math>\omega (p)</math> 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]], <math>\left(\frac{\Delta}{\varpi}\right)</math>.  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.<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|bibcode=2003MaCom..72..499J|url=http://www.ams.org/mcom/2003-72-241/S0025-5718-02-01418-7/S0025-5718-02-01418-7.pdf|doi-access=free}}</ref><ref>{{Citation |last=Guy |first=Richard K. |url=https://books.google.com/books?id=1AP2CEGxTkgC |title=Unsolved problems in number theory |publisher=Springer |edition=3rd|year=2004 |isbn=978-0-387-20860-2|page=8}}</ref>