2 3 5 7 11 13 17 19 23 and so on

By Grontesca at the English Wikipedia, CC BY-SA 3.0

Ulam Spiral


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


By Claudio Rocchini - Own work, thanks to www.numberspiral.com, CC BY 2.5




By Will Orrick - Own work, CC BY-SA 3.0

Klauber Triangle


In the early 1930s, Klauber proposed a geometric arrangement of primes not unlike Ulam's spiral. In 1932, Klauber presented a paper on a triangular, non-spiral matrix to the Mathematical Association of America demonstrating geometric regularity in the distribution of the primes. The lines of primes in the Klauber triangle meet at 60° angles, while in an Ulam Spiral, they meet at 90° angles.



Andrew Booker:

In order to find a prime quickly, the nth prime program uses a large stored data table to get close to the right answer first, then finishes with a relatively short computation. To see how this works, imagine the number line broken into bins, each of size N, i.e. the first is from 0 to N-1, the second from N to 2N-1, etc. (In my implementation, N equals 19219200.) In the table we store the number of primes in each bin. Then, to retrieve the nth prime, the program adds up the numbers until the sum exceeds n. We then know exactly which bin the nth prime falls into. The prime can then be found using a sieve algorithm on that bin.

The sieve algorithm works as follows. First, we compute a set of base primes to be used in sieving. The base primes consist of all the primes up to the square root of the last number in the bin. Second, we keep an array (the sieve) which holds a flag byte for each number in the bin. (Actually, in practice the array is much smaller than the size of a bin, so the bin is first broken into many sub-bins that are sieved one at a time.) We then "sieve" the bin by crossing out (setting the flag byte for) the multiples of each base prime. At the end, the numbers that were not crossed out (did not have their flag bytes set) are all the primes in the bin. These primes are counted until reaching our original number, n. (For a better description of sieve algorithms, see this entry in Chris Caldwell's Prime Glossary.)

Thus, if the bin size is small enough, the sieving can be done very quickly. In this way, most of the work in finding a prime was done in computing the data table. The table, in turn, was computed using a modified sieve algorithm that is well suited to sieving many bins. The modified algorithm actually sieves many times, once for each residue relatively prime to some number with many small prime factors. (I used 30030 = 23571113.) So, for example, in the first sieve, all of the numbers have remainder 1 when divided by 30030, so instead of having the flag bytes represent 0,1,2,... as in the standard sieve algorithm, they represent 1,1+30030,1+230030,... This may sound like it creates more work than before, but it turns out to be faster since we only need to consider remainders which are relatively prime to 30030. In this way, the multiples of 2,3,5,7,11, and 13 are automatically eliminated, making the algorithm roughly 6 times faster. What's more, the modified algorithm can be easily parallelized, as many computers can each work on separate residues. The table used by the nth prime program was calculated over 9 hours by a lab of UltraSparcs and SGIs.


(scratchpad scribbles)

>>> primes[:11]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
>>> t = 1
>>> for p in primes[:11]:
...   t *= p
...   print('%2d %12d' % (p, t))
 2            2
 3            6
 5           30
 7          210
11         2310
13        30030
17       510510
19      9699690
23    223092870
29   6469693230
31 200560490130
  • There are 12,283,531 primes less than or equal to 223,092,870.
  • The 12,283,531st prime is 223,092,827.
    • 223092870 / 16 = 13943304.375 (approx 14 MB)
  • There are 8,028,643,010 primes less than or equal to 200,560,490,130.
  • The 8,028,643,010th prime is 200,560,490,057.
    • 200560490130 / 16 = 12535030633.125 (approx 12.5 GB)

Posted Sun Nov 21 13:16:27 2021 Tags: