Wednesday 22 February 2012

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?

3 comments:

  1. Hi

    I'm interested in this too. You're right that the pattern is based on concentric squares. If you assign an index number, r, to each such square, starting with r = 1 for the square containing 2 to 8, then look for quadratics based on r, all the key Ulam lines emerge. Have a look at this page:

    http://www.apophenia.freeuk.com/ulam.htm

    Cheers

    ReplyDelete
  2. Thanks, I like the look of those charts, they give a wider picture of the patterns I've been talking about. I'll put a link up in a post.

    ReplyDelete
  3. I know this is years later, but I've been running C++ for months in
    search of even richer prime-producing equations than Euler's,
    many of which are of the same form, n^2 + n + k.

    Euler's is easy to surpass in this aspect, but it's far tougher to beat one
    that Jacobsen and Williams have discovered. The first few primes that
    may ever divide it are 229, 239, 269, 277, and 379. I especially hope to
    discover some with significantly smaller factors than 229, as the first
    possible divisor isn't a very thorough judgment, but Jacobsen and
    Williams eliminated primes < 200 during their searches.

    Using Euler's as an example, the first possible factors are 41, 43, and 47.
    For f(n) = n^2 + n + 595937, the first three are 29, 43, and 109. Due to
    the much larger jumps between possible factors of this function, it
    winds up with a substantially higher prime density. Try copying
    595937 into the "Start spiral" box in Dario Alpern's applet:

    www.alpertron.com.ar/ULAM.HTM

    ReplyDelete