Ulam Spiral: a partial explanation

OK, I've done some work on this and I think there are at least a few interesting points that can be made about the Ulam Spiral based on looking at composite numbers as the difference between two squares. Here are a few basic points:

1) Any odd composite number can be expressed as N^2 - M^2 where one of N and M is odd, one is even and N - M > 1. (This should be self-evident, as it is the basis of Fermat factorisation).

2) The Ulam Spiral works by arranging numbers into their squares (eg the first 9 numbers form a square, as do the first 16 etc). This produces a pattern where the half diagonals can be expressed as quadratic polynomials with a second difference of 8. (Half diagonals start from the centre if you divide the square from NW to SE in my version though some versions flip this). There's a nice explanation of this bit here so I won't repeat it. Also the animation on this page is great for showing the polynomials (put the mouse over a diagonal in the diagram and the polynomial is calculated in the box below).

3) So in the image below, we find the square numbers arranged down two half-diagonals, one for the odd squares (centre to SW, blue) and one for the even squares (centre to NE, beside the yellow diagonal).

4) Ignoring the even diagonals (every other diagonal) this creates the following regular pattern. The odd squares can all be expressed as 8N+1 (where N is a positive integer) so they are all 1 mod4. The adjacent diagonal is 2 mod4 larger, so contains only numbers that are 3 mod4. So the diagonals running from bottom left to top right alternate between containing only 1 mod4 numbers and only 3 mod4 numbers.

5) A composite number that is generated by subtracting an odd square from an even square is always a 3 mod4 number (because even squares are all 0 mod4 and odd squares are all 1 mod4).

6) A composite that is generated by subtracting an even square from an odd square is always a 1 mod4 number (for the same reason as above).

7) This is why the individual patterns for N^2 - M^2 composite numbers keep hitting the same diagonals - something I observed in the previous post but didn't explain. For instance the light green pattern for N^2 - 16^2 can be seen to stick to every other diagonal (SW to NE) - because the resulting composite number is always a 1 mod4 number.

8) There are further patterns in the way the diagonals relate to 2^n numbers (eg 4, 8, 16...). For instance look at the series of odd squares 1, 9, 25, 49, 81... Two out of four  (starting with 1 and 49) are 1 mod 16, the other two are 9 mod 16. Two out of every eight are 1 mod 32, two out of every sixteen are 1 mod 64 and so on. The N^2 - 1 (for even N) diagonal (1, 3, 15, 35...) shows a similar pattern, but starts by alternating 1 mod 4 and 3 mod 4, with one in 4 being 1 mod 8 and so on. (This pattern is very similar to the one I was looking at in the earlier posts about composite numbers adjacent to values of 3 * 2^n - I'll return to this soon.)

9) This pattern then fixes the modular values (mod 2^N) of each the odd diagonals that run from top left to top right, since these increase by 2 or fall by 2 as you move up and down the odd diagonals.

10) All of these patterns are significant because they mean this is a long way from being a random array of numbers and already contains a great deal of structure based on modular residues as you move along the rows, columns and diagonals.

11) Finally, the pattern of primes in this pattern is essentially what is left in the odd columns once we remove a pattern of composite numbers. Since all odd composite numbers can be expressed as the difference between two squares (1) we can see how these patterns build up as we move up through the square numbers.

12) The grid above shows the pattern created by N^2 - P^2 for these values of P:

N^2 Blue
N^2 - 1 Yellow
N^2 - 4 Beige
N^2 - 9 Pink
N^2 - 16 Pale green
N^2 - 25 Orange
N^2 - 36 Purple
N^2 - 49 Green

All but the first in each pattern must be composite numbers (eg 7^2 - 6^2 = 13 which is prime but 9^2 - 6^2 = 55 which is composite etc)

If we start with the even values of P, we can see a clear pattern developing. N^2 follows a diagonal to the centre. As N falls, N^2 - 4 follows a parallel path then turns left, skipping one SW to NE diagonal. N^2 - 16 follows another parallel path then turns left, skipping one diagonal each time. When it then turns left again it skips one SW to NE diagonal at each step and two NW - SE diagonals. Finally for the N^2 - 36 pattern we can deduce another parallel path before the section we can see, which follows the same pattern of spiralling around the centre.

12) So each of these patterns is similar (though on an increasing scale), and is hitting the same NW to SE diagonals.

13) For odd values of P we see the inverse of this, the diagonals come down from the top right before spiralling round, and always hit the diagonals that the even values of P are missing.

14) Without doing a lot of maths we can see that this is a rather fractal style of pattern, with constant overlaying of a self-similar pattern, and we can see reasons why lines are likely to develop both in the composite and prime patterns, and why certain sections of diagonals will be more or less dense in composite numbers).

15) Starting the Ulam spiral on different numbers (eg 41) produces a similar pattern (see the Alperton link above for a visual demonstration). This isn't terribly surprising - if we started it on 25 (for instance), the odd squares would follow the pattern that we see here in the N^2 - 25 pattern. Similarly, for any value of centre square, the odd squares and even squares would settle into a stable pattern which would then dictate the way in which the rest of the pattern developed.

To sum up - this way of looking at the Ulam spiral doesn't answer all the various questions about it, but I think it is a useful starting point nonetheless.

In the next post I want to talk about Euler's prime-generating equation x^2 + x + 41.