Ulam spiral

From Wikipedia, the free encyclopedia
  (Redirected from Ulam Spiral)
Jump to: navigation, search
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 graphical depiction of the set of prime numbers, devised by mathematician Stanislaw 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 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 M. 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[edit]

The number spiral is constructed by writing the positive integers in a spiral arrangement on a square lattice, as shown.

Numbers from 1 to 49 placed in spiral order

The Ulam spiral is produced by specially marking the prime numbers—for example by circling the primes or writing only the primes or by writing the prime numbers and non-prime numbers in different colors—to obtain a figure like the one below.

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 particularly impressive example, with a diagonal containing an unbroken string of 40 primes, part of which is shown below (blue background corresponds to primes, green to numbers with just 3 divisors).

617 616 615 614 613 612 611 610 609 608 607 606 605 604 603 602 601 600 599 598 597 596 595 594 593
618 525 524 523 522 521 520 519 518 517 516 515 514 513 512 511 510 509 508 507 506 505 504 503 592
619 526 441 440 439 438 437 436 435 434 433 432 431 430 429 428 427 426 425 424 423 422 421 502 591
620 527 442 365 364 363 362 361 360 359 358 357 356 355 354 353 352 351 350 349 348 347 420 501 590
621 528 443 366 297 296 295 294 293 292 291 290 289 288 287 286 285 284 283 282 281 346 419 500 589
622 529 444 367 298 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 280 345 418 499 588
623 530 445 368 299 238 185 184 183 182 181 180 179 178 177 176 175 174 173 222 279 344 417 498 587
624 531 446 369 300 239 186 141 140 139 138 137 136 135 134 133 132 131 172 221 278 343 416 497 586
625 532 447 370 301 240 187 142 105 104 103 102 101 100 99 98 97 130 171 220 277 342 415 496 585
626 533 448 371 302 241 188 143 106 77 76 75 74 73 72 71 96 129 170 219 276 341 414 495 584
627 534 449 372 303 242 189 144 107 78 57 56 55 54 53 70 95 128 169 218 275 340 413 494 583
628 535 450 373 304 243 190 145 108 79 58 45 44 43 52 69 94 127 168 217 274 339 412 493 582
629 536 451 374 305 244 191 146 109 80 59 46 41 42 51 68 93 126 167 216 273 338 411 492 581
630 537 452 375 306 245 192 147 110 81 60 47 48 49 50 67 92 125 166 215 272 337 410 491 580
631 538 453 376 307 246 193 148 111 82 61 62 63 64 65 66 91 124 165 214 271 336 409 490 579
632 539 454 377 308 247 194 149 112 83 84 85 86 87 88 89 90 123 164 213 270 335 408 489 578
633 540 455 378 309 248 195 150 113 114 115 116 117 118 119 120 121 122 163 212 269 334 407 488 577
634 541 456 379 310 249 196 151 152 153 154 155 156 157 158 159 160 161 162 211 268 333 406 487 576
635 542 457 380 311 250 197 198 199 200 201 202 203 204 205 206 207 208 209 210 267 332 405 486 575
636 543 458 381 312 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 331 404 485 574
637 544 459 382 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 403 484 573
638 545 460 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 483 572
639 546 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 571
640 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570
641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665

History[edit]

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

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. To understand why some odd diagonals have a higher concentration of primes than others, it is necessary to understand the behavior of the corresponding quadratic polynomials modulo odd primes.

Hardy and Littlewood's Conjecture F[edit]

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 4x2 − 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 4x2 + 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. Hardy and Littlewood's formula for the constant A is

A simpler, but obviously equivalent formula is given by:

, where runs over all primes, and — is number of zeros of the quadratic polynomials modulus 'p'.

It further simplifies to .

In the first formula, explanation is a little bit more complex. There, in the first product, p is an odd prime dividing both a and b; in the second product, 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 is the Legendre symbol. A quadratic polynomial with A ≈ 11.3, currently the highest known value, has been discovered by Jacobson and Williams.[8][9]

Variants[edit]

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

References[edit]

  1. ^ a b Gardner 1964, p. 122.
  2. ^ Stein, Ulam & Wells 1964, p. 517.
  3. ^ Gardner 1964, p. 124.
  4. ^ a b Daus 1932, p. 373.
  5. ^ Stein, Ulam & Wells 1964, p. 520.
  6. ^ Gardner 1971, p. 88.
  7. ^ Hartwig, Daniel (2013), Guide to the Martin Gardner papers, The Online Archive of California, p. 117 .
  8. ^ 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, doi:10.1090/S0025-5718-02-01418-7 
  9. ^ Guy, Richard K. (2004), Unsolved problems in number theory (3rd ed.), Springer, p. 8, ISBN 978-0-387-20860-2 

Bibliography[edit]

External links[edit]