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?

Fermat Factorisation

Incidentally, when I am talking about composite numbers as the difference between two squares, I am talking about what is generally known as "Fermat factorisation".

I should have mentioned or realised that sooner, but I am mostly working stuff out for fun here, and then occasionally trawling round to find proper mathematical accounts of the same subjects.

OK, I'm off to read a bit more about quadratic sieves etc as that may help me also.

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.

Ulam Spiral (Gann Square) and differences between square numbers Part 2

I just want to look at the sequences of composite numbers expressed as the difference between two squares in an Ulam spiral.

In this one I've coloured in odd composites as follows:

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

I haven't gone any higher than this, so not all composite odd numbers are coloured.Even numbers are grey and make up half of the diagonals on the diagram.

A few could have been coloured in more than one way (for instance 9 is 5^2 - 4^2 but also 3^2).

Bear in mind that the first in each sequence may not be composite, for instance 3, 5, 7, 11 are primes - but all subsequent instances are composites.

The thing I like in this image is that it picks out clearly what I was saying in the previous post. Each of the coloured routes above has essentially the same form - it eventually settles down into a consistent diagonal, prior to that it spirals around, and follows more oblique diagonals for spells (this behaviour will be extended for larger squares).

I'm also interested to see that where the patterns are spiralling out before settling down, each colour tends to hit the same diagonals, for instance in the N^2 - 49 pattern, 35 and 735 are on the same diagonal, so are 627 and 51, 527 and 147, and 207 and 351.

Also there is an alignment on the diagonals in the oblique sections of the N^2 - 4^2 pattern and the N^2 - 6^2 pattern - 105 and 405, 153 and 493, 209 and 589, and 273 and 693 are on the same diagonals. The same is true of the oblique section of the N^2 - 3^2, N^2 - 5^2 and N^2 - 7^2 patterns. It would be interesting to see how consistent this alignment is with higher numbers as it may also help to concentrate composite numbers on certain diagonals.

I'll give a partial explanation of these last two alignments in a later post, having done a bit of reading about polynomials and the Ulam spiral. Meanwhile I do find this diagram at least starts to help me understand why primes concentrate in particular diagonals on the Ulam spiral.

Ulam Spiral (Gann Square) and differences between square numbers

Nb: the post below was my first attempt at understanding this - there is a more streamlined version here:

I've borrowed the image below from an interesting website that connects the Ulam Spiral with the Gann Square (the latter being a voodoo technique used by chartist stock gamblers). It has a pretty good account of how laying numbers out in this way results in the diagonals describing parabolas. The grey areas are primes, and the thing that fascinated Ulam is the way that these tend to fall on particular diagonals.

 I just want to note that this can also be seen in the light of composite odd numbers always being expressable as the difference between two squares. (something I've looked at in previous posts).

It is fairly obvious that the square numbers fall on two diagonals of this chart, running from bottom left to top right. The equations for the diagonals are given in the linked article as quadratic polynomials/parabolas. Take the diagonal to the North East corner, which contains a high concentration of primes. The numbers are 5, 17, 37, 65, 101, 145, 197, 257, 325, 401.

If we look at how these can be expressed in terms of the nearest square numbers above them, we can rewrite the list in terms of N^2 - X thus:

3^2 - 4
5^2 - 8
7^2 - 12
9^2 -16
11^2 - 20
13^2 - 24
15^2 - 28
17^2 - 32
19^2 - 36
21^2 - 40

(Edit - I should also note that this can be expressed as (2N+1)^2 - 4N)

Of these, there are three cases where that can be rewritten as N^2 - M^2 (all composite except for 3^2 - 4, where the difference between N and M is 1). Of the others, all are prime except for 145 (which can be expressed as 17^2 - 12^2).

Another diagonal is 31, 59, 95, 139, 191, 251.

These can be expressed as:

6^2 - 5
8^2 - 5
10^2 - 5
12^2 - 5
14^2 - 5
16^2 - 5

Different diagonals can be expressed in similar ways as N^2 - X, where X is either a constant value or increasing by a constant value at each stage.

The point about this is not that any diagonal is going to be guaranteed to contain a high number of primes. But odd numbers that can't be written as N^2 - M^2 are always prime, and it's instinctively fairly obvious why some sequences will contain a higher proportion of such numbers than others.

The more important point is that there are diagonal squences which will never contain primes. Obviously the even diagonals contain no primes (other than 2). And there are odd diagonals that will also be prime-free.

For instance, look at the sequence 21, 45, 77, 117, 165, 285, 357, 437. This can be rewritten as N^2 - 4 for all odd numbers from 5 upwards. So this sequence will contain zero primes as it continues upward.

For me  this is a first step to understanding why the Ulam spiral produces those diagonal patterns of primes and composites. As the pattern expands there are more and more odd diagonals which cannot contain primes. The other odd diagonals must contain all the primes therefore the pattern focuses on these spirals. Of course there is a deeper complexity to the pattern but some of this can also be explained using the difference between two squares.

For instance look at the pattern drawn by N^2 - 16. 9 and 33 are on a straight line, but then 65, 105, 153, 209, 273 run down an oblique diagonal (then the pattern jags back to the left down a simple diagonal). As we deal with larger squares, these kinds of oblique diagonal runs of composites will become longer.

Finally there are straight lines like 3, 33, 95, 189, 315, 473 (odd numbers only) which can be expressed thus

2^2 - 1^2
7^2 - 4^2
12^2 - 7^2
17^2 - 10^2
22^2 - 13^2
27^2 - 16^2

There is an obvious mathematical sequence here, N^2 - M^2 with N increasing by 5 and 3 respectively each time.

People have often looked at the Ulam spiral in terms of the formulas that generate a high proportion of primes. I think it maybe makes more sense to look at how composite numbers will cluster in particular odd diagonals, thus leaving the other diagonals to be more densely populated with primes.

I'll elaborate slightly on this in the next post...

Self-similarity in composite patterns (expressed as difference of two squares) Part 2

OK, the thing I want to look at next is the sequences that develop within this grid when we look at N^2 - P^2 for a fixed value of N-P (for instance 12^2 - 7^2, 24^2 - 19^2, 36^2 - 31^2 etc where N - P = 5)

In the image below, the coloured squares are composite numbers adjacent to multiples of 48.

The (non-blue) squares are coded thus:

N-P = 5 Yellow
N-P = 7  Orange
N-P = 11 Green
N-P = 17 Red
N-P = 23 Mauve
N-P = 41 Purple

You can see that each of these series progresses down a diagonally repeating position within the pattern. It is also evident that the series for N^2 - P^2 moves up and down in steps of P, for instance, for N - P = 5  the pattern is -18, -13, -8. -3, 2, 7, 12, 17, a difference of 5 each time.

This is the basic reason why, in the grids we have been looking at in previous posts, there is a self-similarity in the pattern as we move up to composites adjacent to multiples of 48, 96, 192 etc. For instance to get the pattern for N^2 - P^2 numbers adacent to multiples of 96, we halve any even numbers in the sequence above and eliminate the odd numbers, and we get a pattern of -9, -4, 1, 6. Then for numbers adjacent to multiples of 192, we do the same thing and get a pattern of (-7), -2, 3, (8).

These series repeat with regular periodicity. In terms of twin prime candidate pairs (in other words pairs of 6N+1 and 6N-1 numbers that are 2 apart), the pattern for N^2 - 5^2 repeats in a cycle of 2 (you can see above that the pattern for 192 hits the same pairs as the pattern for 48 - the signs are reversed meaning that it is a negative version of the same pattern but the same pairs are nonetheless present).

The specific reason for this can be seen when we look at the results in terms of mod 4 arithmetic. For N^2 - 5^2 the pattern in mod4 can be seen as -2 (=2) -1 (=3), 0, 1, 2, 3, 0, 1, increasing by one each step. For N^2 - 7^2 the pattern in mod 4 will decrease by one each step. And since any odd number must also be a 4N+/-1 number, the pattern will always increase or decrease by one at each step.

This means that when we double the target by going up from composites adjacent to 48 to those adjacent to 96, 192 etc, we eliminate every other number in the series. If you look at the yellow squares above, there are eight in the larger square, and four in the medium square. Out of these numbers 4 are divisible by 2, 2 are divisible by 4 and one is divisible by 8.

I'll talk more about these series in later posts.

The only other thing to point out at this stage is how the pattern for N - P = 41 (purple) behaves. There are none in the top left square of the diagram, so does this mean it is a discontinuous series?

Well no - instead you can see it like this:

48^2 - 7^2 = 2255
24^2 - (-17)^2 =  287 (which is 41*48 less than 2255)
0^2 - (-41)^2 = -1681 (which is 41*48 less than 287)

And 24^2 - 17^2 is already in the pattern in the N - P = 7 diagonal. So this is effectively filling the gap in the N - P = 41 series also.

(Just a reminder, the minus numbers are there because of the way the grid works, meaning we get 0^2 - 41^2 rather than 41^2 - 0^2. You can basically ignore the minus sign, or bear in mind that the minus numbers are 6N+1 numbers while the positive ones are 6N-1 numbers).

Of course this is rather obvious since the series above can be rewritten as

41 x 55
41 x 7
41 x 41 (when you ignore the minus signs)

So effectively we are just seeing that the series of multiples of 41 (or any other odd prime) will only hit a number adjacent to a multiple of 48 twice in every 48 steps (once on a 48N+1 number and once on a 48N-1 number). This isn't terribly surprising, but I still find it interesting to view it as the difference between two squares rather than as a series of multiples.

In the next post in this series I want to talk about the way that composite numbers are distributed as a result of the modular patterns mentioned above.

(First I am going to break off and take a look at the Ulam Spiral though).