**Primal Screens**
'''or Investigating Prime Numbers when plotted in the Ulam Style —''' [KWJ] 

Sorry for the Pun Intended.  Currently, my only Primal Scream is "Done!!".  I've meant to write this up for several years, but have been interrupted many times.  A strange side effect of the interruptions is that I've had to go back and figure out what I'd done previously, and in the process discover something new that I'd not seen before.  

This contribution is also meant to brag about Tcl/Tk, which was used to create [Prime Number Browser].  The browser was designed to answer some questions about the distribution of prime numbers when they are plotted in the Ulam Style.  Tcl/Tk has proven to be a great vehicle for stumbling about and discovering pretty pebbles on the beach of prime numbers.

Browsers might be described as "aha!" generators, perhaps based on a conjecture by Yogi Berra who once said, "You can observe a lot just by watching".  The Prime Number Browser displays prime numbers on two Primal Screens, one plotted on a Coarse Grid, the other on a Fine Grid.  If we think of the integers from 1 to a very large number as being connected like a string of pearls, then the Ulam method consists of laying them out in a spiral pattern on a square grid, starting with 1 at the center.  An excellent description and demonstration of the Ulam method by [Gerard Sookahet], can be found on the Wiki at [Ulam spiral].

----
[http://www.kb-creative.net/images/ulam/UlamSpiral_1.png]


The first figure shows a portion of the set of all prime numbers less than 100,000, plotted on the Fine Grid.  Each plus represents a prime number.  As originally observed by Ulam, the primes do not fall in a random pattern, but certain directions are rich in primes.  

On the plot are two blue reference lines and two black diagonal lines which traverse the upper left and lower right quadrants. Although not obvious at this scale, these lines pass through integers which are perfect squares.  The upper left line passes thru numbers which are of the form `y = m²`, where m is an even number.  The lower right line passes thru values where m is an odd number.  The prime rich directions appear to be either parallel or perpendicular to these lines of even or odd squares.  

Finally, in order to give a sense of scale, the black square outline near the center represents the extent of the Coarse Grid Primal Screen, overlaid on the Fine Grid.

When carefully examined, figure 1 reveals what looks like an empty channel running off to the right, just below the positive blue horizontal axis.  There is a similar vertical empty channel running downward and to the left of the negative blue vertical axis.  One might ask — "Are these channels truly empty?  Are there formulae which might predict such channels?"  These were some questions the browser helped me answer.  Other obvious questions were — "Are there formulae that one might use to predict prime numbers along any of the prime rich directions?  What would such formulae look like?"


[http://www.kb-creative.net/images/ulam/UlamSpiral_2.png]


The second figure shows a portion of a smaller set of primes, plotted on the Coarse Grid.  Here again, we see the blue reference axes as well as the black lines of even and odd squares.  At this resolution, the prime numbers are identified in blue.  Non primes are in gray.  It is clear that the lines of even and odd squares do indeed run through integers which are perfect squares.  The ability to see individual numbered cells in this manner was a great help in trying to analyze the ways in which primes are distributed.

**Empty Channels**
At this resolution, we see that the empty channels mentioned earlier are actually two rows of numbers extending off to the right, starting with the numbers 9 and 24.  There are also two columns of numbers descending to the bottom, starting with numbers 21 and 22.  At this resolution, we also see another empty channel, just to the right of the upper blue vertical axis starting with the integer 14, and finally, just above the negative blue axis an empty channel extending to the left, starting with 18. 

Regarding the question of whether or not formulae exist which predict the empty channels, the Coarse Grid gives us a hint, in that the lines of even and odd squares intersect numbers of the form,  `y = m²`, for m in the range 1 to infinity. In this case, `y` is always non prime.  If we look carefully at this resolution, we can see just above the line of even squares what appears to be another empty channel containing numbers like 15, 35, 63, 99, etc.  These numbers are of the form `y = m² -1`, which when rewritten as `y = (m+1)(m-1)`, is always a non prime number.  A similar empty channel lies parallel and below the line of odd squares.

With these encouraging results, perhaps there is hope for finding formulae which predict prime numbers, based upon the lines of even and odd squares.

**Prime Predicting Formulæ**
In figure 2, there is a line of prime numbers below the line of odd squares starting with the integers 7, 23, 47, 79, 167 etc.  These primes are related to numbers on the line of odd squares.  47 is two integers to the left of 49, which is 7², 79 is two integers to the left of 81, which is 9².  Pursuing further, we see that these primes are all of the form
===
y = m² - 2   ''for odd m''  
===
Similarly there is a line of primes parallel to and beneath the line of even squares starting with the integers 43, 71, 107, 151, 263 etc.  After searching around a bit, we find that 43 is seven greater than 36, which is 6².  71 is seven greater than 64 which is 8².  The prime numbers along this line then, are of the form `y = m² + 7` for even m.  This is not to say that every number these formulae predict are primes, but they do account for some primes along a certain prime rich direction.  We will see that there are other prime predicting formulae which are more potent at predicting primes than others.

[http://www.kb-creative.net/images/ulam/UlamSpiral_3.png]


Figure 3 shows the results of the above two formulae plotted on the Coarse Grid.  The set of primes of the form `y = m² - 2` are colored in Steel Blue, non primes in chartreuse.  For `y = m² + 7` the primes are colored in red, and non primes in beige.   

Several things are interesting in this figure.  First, each formula predicts two branches of numbers, one of which contains some primes, while the other branch appears totally empty.  The branches are also parallel to and equidistant from the lines of squares.  Second, the empty branches correlate with the sign of the second term in the formula `y = m² + B`.  For `B` negative, non-primes are predicted for even values of `m`.  For `B` positive, non-primes are predicted for odd values of `m`.  Third, primes fall into two distinct regions.  There is a sort of confused region near the origin for small values of m, but at a certain point an asymptotic behaviour develops into a line parallel to one of the lines of odd or even squares.


**Are There Other Kinds of Formulæ?**
About the time I was discovering these simple formulae, I stumbled on a very interesting reference at 
[http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html].  

This reference shows a table of low-order polynomials which generate prime numbers.  The emphasis of the table seems to be on polynomials which predict the longest continuous sequence of prime numbers.  The formulae here are all a bit more complex than the ones we've mentioned so far.  I've limited my investigations to polynomials of second degree in m, and with smaller coefficients.  Otherwise predictions soon exceed the prime number base of numbers less than 100,000.

It's interesting  that those old rascals, Euler and Legendre had been down the Prime Number generation path a long time ago.  Working diligently, probably with quill and ink, Euler discovered the formula `y = m² - m + 41` back in 1772.  Some time later, Legendre proposed the formula `y = m² + m + 17`.  Dropping these equations into the browser, I saw something like figure 4, plotted on the Coarse Grid. 
 

[http://www.kb-creative.net/images/ulam/UlamSpiral_4.png]


The Euler formula generates an impressive number of primes, here plotted in Navy Blue.   Not quite as potent, but still impressive, the Legendre formula primes are plotted in Dark Green and the non primes in yellow. 

[http://www.kb-creative.net/images/ulam/UlamSpiral_5.png]


Figure 5 shows the trajectories of these formulae when plotted on the Fine Grid.  Note that the formulae predict two branches, both of which contain primes.

It's apparent that the Euler equation traverses one of the heaviest prime rich directions found in Figure 1.  It also shows the characteristic "confused" region near the origin and assymptotic behaviour further out.  Note also that the asymptotic direction for these  formulae is perpendicular to that of the simpler equations of Figure 3.

**Two More Interesting Formulæ**

[http://www.kb-creative.net/images/ulam/UlamSpiral_6.png]


Figure 6 shows the trajectories of two more interesting formulae, and illustrates the value of a browser.  The trajectory in steelblue and yellow was generated by  `y = m² - 227`.  Again, based on its simple polynomial form, we see two branches, one ultimately going to the left and downward, which is empty, and the other going upward, and containing primes.  The second trajectory in darkgreen and yellow was generated by  `4m² + 4m + 59`.  

Both of these formulae illustrate the aha property of a browser.  Until seeing this plot, my assumption was that a trajectory took on an asymptotic behaviour that forever remained straight.  Perhaps that was "Leaping to a Contusion".  Maybe trajectories really have a spiral behaviour if we only look far enough out at larger sets of primes.  Also, the second polynomial has only one branch, perhaps related to the even coefficients.  Figure 6 is a portion of a full resolution plot of all primes less than 200,000.

[http://www.kb-creative.net/images/ulam/UlamSpiral_7.png]


In Figure 7, we see the "trajectory" of the polynomial `y = 2m² + 29`.  This is a full resolution plot of all primes less than 200,000.  Predicted primes are red, non primes are yellow.  At this point the "trajectory" appears to be all "confused behaviour", there is no hint of asymptotic behaviour.  I think the only hope of seeing such would be to extend the list of prime numbers to a much larger set, say those which are less than 1,000,000, and some way of reducing the individual cells to a few pixels.  Future grist for the mill.
----


**Potency**
A final point of interest is in what I call the Potency of a given prime generating formula.  This is the percent of Primes that an equation predicts out of a total number of predictions.  The following table shows the potency for various formulae:
!!!!!!
%|                         | Potency        |                  |%
%| Formula         | Coarse Grid | Fine Grid |%
&| `M² - 2`       | '0.2384'        | '0.2114'  |&
&| `M² + 7`       | '0.2715'       | '0.2145'   |&
&| Legendre       | '0.4574'       | '0.4574'   |&
&| Euler               | '0.8026'       | '0.6981'  |&
&| `2*M² + 29` | '0.8194'      | '0.640'     |&
!!!!!!
The Coarse Grid has a limit of 152 predictions, the Fine Grid limit is 318 predictions.  It appears the potency diminishes as the number of predictions increases.  Is there a limiting value to the potency as we increase the number of predictions?  Again, we need to search through higher numbers of primes.

To conserve space here, most all of the plots have been reduced to 2/3 their normal size.

The Tcl/Tk script for the browser is found at [Prime Number Browser].  A small script demonstrating the Ulam method is found at [Ulam Spiral Demo].

**Other Visualizations**

Inspired by this article I played in an interactive wish (8.5 or later).
(Feel free to move this somewhere else, as it is not directly related to the spirals.)

======
set l [read [open primes.txt]];llength $l;# who cares about the open file?
canvas .c; pack .c -expand yes -fill both
bind .c <1> {.c scan mark %x %y }
bind .c <Release-1> { .c scan dragto %x %y 1 }
proc dot {x y} { .c create line $x $y $x [expr {$y+1}]}
proc pdot {p} {set r [expr {isqrt($p)}];set phi [expr {$p-$r*$r}];dot [expr {$phi-$r}] $r}
foreach p $l { pdot $p }
======

You can use the Mouse to scroll (by dragging), but it won't move until you release.
(You can also bind to B1-Motion, but it is no fun, once you have a million points on the canvas.)

<<categories>> Graphics | Mathematics