Prime Spirals (Node.js, Express, MongoDB, etc..)

January 31, 2013


I was doodling a spiral of natural numbers the other day, making big dots for the primes and I started to notice that primes seemed to be showing up frequently on the corners. Then I noticed patterns of broken lines appearing -- vertical, horizontal and diagonal. The human mind has a tendency to see patterns everywhere -- even in randomness, so I asked my daughters for their opinions. It seemed to us that there was structure there, but we weren't sure. We needed to see more points. So I wrote a little HTML5 canvas application to calculate primes and plot the spiral for various canvas dimensions (It doesn't require a server, you can just open the html file in a browser to use it).

Of course, I wasn't the first to stumble upon this odd phenomenon of structure appearing when primes are plotted in a spiral -- Ulam is credited with the discovery in the sixties, but I wouldn't rule out the possibility that it was observed much earlier.

The canvas application revealed a great deal of structure in the primes when displayed this way -- and raised lots more questions. Why should a spiral reveal structure in an such an apparently random set? What if we try different spiraling methods (triangular, etc...)? What if we include non-primes using a grayscale or color palette to indicate their number of factors? Time to get to work and add a few more features...

An important question is: Do the lines (albeit with gaps) extend out forever? -- if so, there should be a higher probability of finding a large prime if we extrapolate along the lines. But what is the equation of a line on a plot created by this spiraling technique?

Consider the difference between successive terms along diagonal lines beginning at 1: We get {4, 12, 20, 28 ...} going down and left, {2, 10, 18, 26, ...} going down and right, {6, 14, 22, ...} going up and left and {8, 16, 24, ...}. Notice that the second order difference (the difference of the differences) is 8 in all cases! In fact this is the case for all diagonal lines, not just those beginning at one. The general formula for a diagonal line turns out to be:
 x = a + (b-4)*n + 4*n^2
where a and b are constants and n can be thought of as the number of passes around the spiral.

This equation has the shape of an upward curving parabola and works for both positive and negative values of n. It explains quite a few observations, such as the fact that all the powers of 4 lie along a diagonal line extending down and left from the origin.

It turns out that this formula works for horizontal and vertical lines too -- so long as they only cross the arrow lines in the figure and don't overlap them.

Adding the ability to display non-primes on a grayscale revealed even more intricate structure, but introduced quite a bit of additional computation. It began to seem silly to recompute and count factors every time a plot was generated, so I added a server application built on Node.js, Express and using MongoDB to store and fetch numbers along with the count of their factors. I'm currently hosting it here.

This client server application is designed so that numbers are also stored on the client side (i.e. in Javascript). When more numbers are needed for generating a plot than are currently stored on the client, these are fetched from the server and stored on the client.

When numbers are requested that exceed the maximum stored on the server, the factorization is performed on the client. The newly factored numbers are added to the client storage and pushed to the server. This approach eliminates the risk of excessive resource usage at the server and makes the burden of computing new factorizations a collective endeavor, shared by those with the desire to explore ever larger numbers.

If you want a challenge, try working out the equation for primes in a line on the triangular spiral plot, I haven't gotten around to that yet... Is a line on the triangular plot also a line on the square plot? -- In general, I think not. But what is their relationship? Have fun!

Feedback

Your feedback is welcome! If you find any errors in this post or have any additional pointers or insights, please take a moment to register and share your thoughts.



No Comments Yet

You must be logged in to comment

All Posts