Ulam’s primes

Searching for prime numbers has been a topic that many mathematicians have dedicated their time to over the years. Being able to generate prime numbers, and test if a number is prime quickly is an important problem in the field of computer science, as this would lead to major problems in encryption.

One of these mathematicians that enjoyed spending their time finding primes was the polish physicist/mathematician Stanislaw Ulam. Although he may be more commonly known for his works on the Monte Carlo method, or the Manhattan project. He also came up with an interesting idea concerning primes.

If you write out all numbers from 1 to N in a spiral, where you start at 1 in the center and go outwards in a counter-clock wise manner, you are left with a spiral of numbers (Ulam’s Spiral). This in itself is not that interesting, even to a mathematician. However, if you start to highlight all the prime numbers that you find you will start to notice patterns.

Ulam spiral with values from 1 to 100, all primes have been highlighted.

If you look at the image above, in first instance you will not see much, this is because the behavior we are hinting at is better seen at a larger scale. However, If you look at the primes 5, 19, 41, 71 you can see that they are positioned on a diagonal line. The same goes for the primes 19, 7, 23, 47, 79.

As many things in mathematics, this may just be a coincidence. So to get a better idea of what is happening we zoom out and plot all the primes in the spiral in a scatter plot.

Ulam spiral where all the primes are represented by dots.

Now it indeed does look like there is a trend going on in the data, some diagonals seem to have a far higher ‘prime density’ than others, but does this tell us anything about finding new primes? Unfortunately, it does not. These diagonals that can be seen to have a higher ‘prime density’ than others, can be seen as prime generating polynomials.

Prime generating polynomials have been around for longer than Ulam’s spiral, however there is no proof that a perfect, all numbers are prime, prime generating polynomial exists. Also, there is no guarantee that the polynomials that seem to have a high prime density close to the middle (1), will continue to have a higher likelihood of generating primes for bigger values.

The general formula that will give any diagonal in a Ulam spiral is given below. It should be noted that for the polynomials with the highest prime density there is no guarantee that all numbers are prime, as a matter of fact they never are. Also that this formula gives all diagonals, so also ones that contain no primes.

To demonstrate these prime generating polynomials we have highlighted the primes generated by one of these polynomials, that also had a high density.

Ulam spiral with primes of 4n^2 – 2n + 41

Now, does all this information help us in any way? Currently it is difficult to say, seeing as there is no polynomial that has been proven to only generate primes, it could be contained somewhere in this spiral. However, we can also not guarantee that a polynomial has a asymptotically high prime density, which would make it a good prime generator. So for now, it could be useful, but we haven’t found how.

Leave a comment

Your e-mail address will not be published. Required fields are marked *