# Ulam spiral

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).

The Ulam spiral or prime spiral 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

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

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 (from 1523 to 1601), the longest example of its kind[5]. Part of this diagonal is shown in the spiral below, with blue background corresponding to primes, green to squares of prime numbers, and red to numbers with 25 or more divisors.

 2541 2540 2539 2538 2537 2536 2535 2534 2533 2532 2531 2530 2529 2528 2527 2526 2525 2524 2523 2522 2521 2520 2519 2518 2517 2516 2515 2514 2513 2512 2511 2510 2509 2508 2507 2506 2505 2504 2503 2502 2501 2500 2499 2498 2497 2496 2495 2494 2493 2492 2491 2542 2345 2344 2343 2342 2341 2340 2339 2338 2337 2336 2335 2334 2333 2332 2331 2330 2329 2328 2327 2326 2325 2324 2323 2322 2321 2320 2319 2318 2317 2316 2315 2314 2313 2312 2311 2310 2309 2308 2307 2306 2305 2304 2303 2302 2301 2300 2299 2298 2297 2490 2543 2346 2157 2156 2155 2154 2153 2152 2151 2150 2149 2148 2147 2146 2145 2144 2143 2142 2141 2140 2139 2138 2137 2136 2135 2134 2133 2132 2131 2130 2129 2128 2127 2126 2125 2124 2123 2122 2121 2120 2119 2118 2117 2116 2115 2114 2113 2112 2111 2296 2489 2544 2347 2158 1977 1976 1975 1974 1973 1972 1971 1970 1969 1968 1967 1966 1965 1964 1963 1962 1961 1960 1959 1958 1957 1956 1955 1954 1953 1952 1951 1950 1949 1948 1947 1946 1945 1944 1943 1942 1941 1940 1939 1938 1937 1936 1935 1934 1933 2110 2295 2488 2545 2348 2159 1978 1805 1804 1803 1802 1801 1800 1799 1798 1797 1796 1795 1794 1793 1792 1791 1790 1789 1788 1787 1786 1785 1784 1783 1782 1781 1780 1779 1778 1777 1776 1775 1774 1773 1772 1771 1770 1769 1768 1767 1766 1765 1764 1763 1932 2109 2294 2487 2546 2349 2160 1979 1806 1641 1640 1639 1638 1637 1636 1635 1634 1633 1632 1631 1630 1629 1628 1627 1626 1625 1624 1623 1622 1621 1620 1619 1618 1617 1616 1615 1614 1613 1612 1611 1610 1609 1608 1607 1606 1605 1604 1603 1602 1601 1762 1931 2108 2293 2486 2547 2350 2161 1980 1807 1642 1485 1484 1483 1482 1481 1480 1479 1478 1477 1476 1475 1474 1473 1472 1471 1470 1469 1468 1467 1466 1465 1464 1463 1462 1461 1460 1459 1458 1457 1456 1455 1454 1453 1452 1451 1450 1449 1448 1447 1600 1761 1930 2107 2292 2485 2548 2351 2162 1981 1808 1643 1486 1337 1336 1335 1334 1333 1332 1331 1330 1329 1328 1327 1326 1325 1324 1323 1322 1321 1320 1319 1318 1317 1316 1315 1314 1313 1312 1311 1310 1309 1308 1307 1306 1305 1304 1303 1302 1301 1446 1599 1760 1929 2106 2291 2484 2549 2352 2163 1982 1809 1644 1487 1338 1197 1196 1195 1194 1193 1192 1191 1190 1189 1188 1187 1186 1185 1184 1183 1182 1181 1180 1179 1178 1177 1176 1175 1174 1173 1172 1171 1170 1169 1168 1167 1166 1165 1164 1163 1300 1445 1598 1759 1928 2105 2290 2483 2550 2353 2164 1983 1810 1645 1488 1339 1198 1065 1064 1063 1062 1061 1060 1059 1058 1057 1056 1055 1054 1053 1052 1051 1050 1049 1048 1047 1046 1045 1044 1043 1042 1041 1040 1039 1038 1037 1036 1035 1034 1033 1162 1299 1444 1597 1758 1927 2104 2289 2482 2551 2354 2165 1984 1811 1646 1489 1340 1199 1066 941 940 939 938 937 936 935 934 933 932 931 930 929 928 927 926 925 924 923 922 921 920 919 918 917 916 915 914 913 912 911 1032 1161 1298 1443 1596 1757 1926 2103 2288 2481 2552 2355 2166 1985 1812 1647 1490 1341 1200 1067 942 825 824 823 822 821 820 819 818 817 816 815 814 813 812 811 810 809 808 807 806 805 804 803 802 801 800 799 798 797 910 1031 1160 1297 1442 1595 1756 1925 2102 2287 2480 2553 2356 2167 1986 1813 1648 1491 1342 1201 1068 943 826 717 716 715 714 713 712 711 710 709 708 707 706 705 704 703 702 701 700 699 698 697 696 695 694 693 692 691 796 909 1030 1159 1296 1441 1594 1755 1924 2101 2286 2479 2554 2357 2168 1987 1814 1649 1492 1343 1202 1069 944 827 718 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 690 795 908 1029 1158 1295 1440 1593 1754 1923 2100 2285 2478 2555 2358 2169 1988 1815 1650 1493 1344 1203 1070 945 828 719 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 689 794 907 1028 1157 1294 1439 1592 1753 1922 2099 2284 2477 2556 2359 2170 1989 1816 1651 1494 1345 1204 1071 946 829 720 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 688 793 906 1027 1156 1293 1438 1591 1752 1921 2098 2283 2476 2557 2360 2171 1990 1817 1652 1495 1346 1205 1072 947 830 721 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 687 792 905 1026 1155 1292 1437 1590 1751 1920 2097 2282 2475 2558 2361 2172 1991 1818 1653 1496 1347 1206 1073 948 831 722 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 686 791 904 1025 1154 1291 1436 1589 1750 1919 2096 2281 2474 2559 2362 2173 1992 1819 1654 1497 1348 1207 1074 949 832 723 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 685 790 903 1024 1153 1290 1435 1588 1749 1918 2095 2280 2473 2560 2363 2174 1993 1820 1655 1498 1349 1208 1075 950 833 724 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 684 789 902 1023 1152 1289 1434 1587 1748 1917 2094 2279 2472 2561 2364 2175 1994 1821 1656 1499 1350 1209 1076 951 834 725 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 683 788 901 1022 1151 1288 1433 1586 1747 1916 2093 2278 2471 2562 2365 2176 1995 1822 1657 1500 1351 1210 1077 952 835 726 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 682 787 900 1021 1150 1287 1432 1585 1746 1915 2092 2277 2470 2563 2366 2177 1996 1823 1658 1501 1352 1211 1078 953 836 727 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 681 786 899 1020 1149 1286 1431 1584 1745 1914 2091 2276 2469 2564 2367 2178 1997 1824 1659 1502 1353 1212 1079 954 837 728 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 680 785 898 1019 1148 1285 1430 1583 1744 1913 2090 2275 2468 2565 2368 2179 1998 1825 1660 1503 1354 1213 1080 955 838 729 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 679 784 897 1018 1147 1284 1429 1582 1743 1912 2089 2274 2467 2566 2369 2180 1999 1826 1661 1504 1355 1214 1081 956 839 730 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 678 783 896 1017 1146 1283 1428 1581 1742 1911 2088 2273 2466 2567 2370 2181 2000 1827 1662 1505 1356 1215 1082 957 840 731 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 677 782 895 1016 1145 1282 1427 1580 1741 1910 2087 2272 2465 2568 2371 2182 2001 1828 1663 1506 1357 1216 1083 958 841 732 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 676 781 894 1015 1144 1281 1426 1579 1740 1909 2086 2271 2464 2569 2372 2183 2002 1829 1664 1507 1358 1217 1084 959 842 733 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 675 780 893 1014 1143 1280 1425 1578 1739 1908 2085 2270 2463 2570 2373 2184 2003 1830 1665 1508 1359 1218 1085 960 843 734 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 674 779 892 1013 1142 1279 1424 1577 1738 1907 2084 2269 2462 2571 2374 2185 2004 1831 1666 1509 1360 1219 1086 961 844 735 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 673 778 891 1012 1141 1278 1423 1576 1737 1906 2083 2268 2461 2572 2375 2186 2005 1832 1667 1510 1361 1220 1087 962 845 736 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 672 777 890 1011 1140 1277 1422 1575 1736 1905 2082 2267 2460 2573 2376 2187 2006 1833 1668 1511 1362 1221 1088 963 846 737 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 671 776 889 1010 1139 1276 1421 1574 1735 1904 2081 2266 2459 2574 2377 2188 2007 1834 1669 1512 1363 1222 1089 964 847 738 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 670 775 888 1009 1138 1275 1420 1573 1734 1903 2080 2265 2458 2575 2378 2189 2008 1835 1670 1513 1364 1223 1090 965 848 739 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 669 774 887 1008 1137 1274 1419 1572 1733 1902 2079 2264 2457 2576 2379 2190 2009 1836 1671 1514 1365 1224 1091 966 849 740 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 668 773 886 1007 1136 1273 1418 1571 1732 1901 2078 2263 2456 2577 2380 2191 2010 1837 1672 1515 1366 1225 1092 967 850 741 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 667 772 885 1006 1135 1272 1417 1570 1731 1900 2077 2262 2455 2578 2381 2192 2011 1838 1673 1516 1367 1226 1093 968 851 742 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 666 771 884 1005 1134 1271 1416 1569 1730 1899 2076 2261 2454 2579 2382 2193 2012 1839 1674 1517 1368 1227 1094 969 852 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 883 1004 1133 1270 1415 1568 1729 1898 2075 2260 2453 2580 2383 2194 2013 1840 1675 1518 1369 1228 1095 970 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 1003 1132 1269 1414 1567 1728 1897 2074 2259 2452 2581 2384 2195 2014 1841 1676 1519 1370 1229 1096 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1131 1268 1413 1566 1727 1896 2073 2258 2451 2582 2385 2196 2015 1842 1677 1520 1371 1230 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1267 1412 1565 1726 1895 2072 2257 2450 2583 2386 2197 2016 1843 1678 1521 1372 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1411 1564 1725 1894 2071 2256 2449 2584 2387 2198 2017 1844 1679 1522 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1563 1724 1893 2070 2255 2448 2585 2388 2199 2018 1845 1680 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1723 1892 2069 2254 2447 2586 2389 2200 2019 1846 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1891 2068 2253 2446 2587 2390 2201 2020 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 2067 2252 2445 2588 2391 2202 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2251 2444 2589 2392 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2443 2590 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641

## 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

${\displaystyle f(n)=4n^{2}+bn+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 ${\displaystyle 4n^{2}+8n+3}$, while producing only odd values, factorize over the integers ${\displaystyle (4n^{2}+8n+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 ${\displaystyle 4n^{2}+6n+1}$ and ${\displaystyle 4n^{2}+6n+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 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

${\displaystyle P(n)\sim A{\frac {1}{\sqrt {a}}}{\frac {\sqrt {n}}{\log n}}}$

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,

${\displaystyle A=\prod \limits _{p}{\frac {p-\omega (p)}{p-1}}~}$,

in which ${\displaystyle \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

${\displaystyle A=\varepsilon \prod _{p}{\biggl (}{\frac {p}{p-1}}{\biggr )}\,\prod _{\varpi }{\biggl (}1-{\frac {1}{\varpi -1}}{\Bigl (}{\frac {\Delta }{\varpi }}{\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 ${\displaystyle \omega (p)=0}$ since p then cannot divide c. The second product index ${\displaystyle \varpi }$ runs over the infinitely-many odd primes not dividing a. For these primes ${\displaystyle \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, ${\displaystyle \left({\frac {\Delta }{\varpi }}\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.[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.

## References

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. ^ 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, 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