Ulam Spiral Explained (Sort of...)

OK, one more post on the Ulam Spiral.

In the last post I mentioned that the half diagonals of the spiral are quadratic polynomials, and gave this link to a nice animation that calculates those polynomials.

One notable polynomial is n^2 + n + 41 - this is Euler's prime-generating equation, which means it creates a diagonal in the spiral that is especially rich in primes. Why is this?

There is a fairly simple explanation based on modular maths. As n increases by 1, the equation increases steadily with the gap becoming 2 bigger at each step (eg the polynomial has a second difference of 2) - 41, 43, 47, 53, 61 etc (increasing by 2, 4, 6, 8...). This means that for the odd prime X, there is a repeating pattern X places long if we convert the series into mod X - for instance in mod 3, this series is 2, 1, 2, 2, 1, 2 and so on, repeating every 3 steps. This is the case for all odd numbers so for mod 5, this pattern will repeat - 1, 3, 2, 3, 1.

Where the repeating pattern for the series expressed as mod X doesn't include a zero, this series will never hit a multiple of X.

As it happens, for x^2 + x + 41, this means that this series doesn't contain multiples of any of the primes lower than 41 - the first composite number it hits is 40^2 + 40 + 41 = 41 x 41, then it also hits 41^2 + 41 + 41 = 41 x 43.

By comparison, the series for n^2 + n + 39 hits zeros for 3, 5, 13, 17, 19, 23, 31, 37 ...

And the series for n^2 + n + 43 hits zeros for 3, 5, 7, 11 , 17, 19, 23...

This means that the series for these polynomials will always contain a higher density of composite numbers, since they will come along at least every three places, with at least one every 5 and at least one every X places for the other primes X for which they contain zeros. No matter how many larger primes X have zeros in the x^2 + x + 41 series, it will never make up for the lack of zeros in those lower primes, so it will always be denser in primes than the two diagonals either side of it.

While this is an extreme case, there is a variation between all the polynomials in the spiral, with some creating very strong biases towards prime numbers, and some creating a bias towards composites. If you play with that animation I linked to, it shows the primes whose multiples each polynomial will always miss in brackets after the polynomial (as you hover the mouse over a diagonal these are displayed beneath the diagram).

 

Finally, here is a visual for x^2 + x +41. It is an extended version of the diagram in the previous post. The blue squares (in two different shades because it alternates between two halves of the diagram) are the numbers generated by x^2 + x +41. Note that this creates a spiral pattern similar to the ones I created using the difference of two squares, but rotating in the opposite direction. It finally settles into a simple diagonal pattern towards the edge of this section and will continue on that diagonal to infinity. As it is a SE to NW diagonal it will cross the square patterns at intervals. Note that the series alternates between 4n+1 and 4n+3 diagonals, so you have to alternate between the light and dark blues to see the whole series develop.

Pretty isn't it?