Checking the ulam spiral

In the following post, the Ulam spiral is described. It’s a very simple object – write down consecutive natural numbers starting from 41 in a square spiral. Curiously, the numbers on the diagonal are primes:

Ulam spiral

Reading this post, I immediately wanted to check how long this property holds. The original blog post suggests:

Remarkably, all the numbers on the red diagonal are prime — even when the spiral is continued into a 20 × 20 square.

Yet it doesn’t mention if it stops there or not. Without peeking (in Wikipedia), I wrote a simple program to check:

import sys
import psyco
psyco.full()
 
UP = 0
LEFT = 1
DOWN = 2
RIGHT = 3
 
DIRECTIONS = {UP: (0, -1),
              LEFT: (-1, 0),
              DOWN: (0, 1),
              RIGHT: (1, 0)}
 
def generate_ulam_seq(n):
    start = 41
    x = 0
    y = 0
    min_x = 0
    max_x = 0
    min_y = 0
    max_y = 0
    value = start
    direction = UP
    for i in xrange(n):
        yield x, y, value
        value += 1
        add_x, add_y = DIRECTIONS[direction]
        x, y = x + add_x, y + add_y
        if x < min_x:
            direction = (direction+1) % 4
            min_x = x
        if x > max_x:
            direction = (direction+1) % 4
            max_x = x
        if y < min_y:
            direction = (direction+1) % 4
            min_y = y
        if y > max_y:
            direction = (direction+1) % 4
            max_y = y
 
def is_prime(n):
    return all(n%x != 0 for x in xrange(2, int((n**0.5) + 1)))
 
def main():
    for x, y, v in generate_ulam_seq(int(sys.argv[1])):
        if x == y and not is_prime(v):
            print x, y, v
 
if __name__ == '__main__':
    main()

Running it, we get:

> ulam.py 10000
20 20 1681
-21 -21 1763
22 22 2021
-25 -25 2491
28 28 3233
-33 -33 4331
38 38 5893
-41 -41 6683
41 41 6847
42 42 7181
-44 -44 7697
-45 -45 8051
-46 -46 8413
48 48 9353

So the property doesn’t hold for a very long time. Reading up on Wikipedia, it seems the Ulam spiral still has interesting properties related to primes in higher sizes. Maybe I’ll plot that one as well in a future post.

PS: Regarding primality testing, this is a cute, quick&dirty one liner. In the range of numbers we’re discussing, it is ‘good enough’.

This entry was posted in Math, Programming, Python and tagged , , , , . Bookmark the permalink.

4 Responses to Checking the ulam spiral

  1. A. deAprix says:

    No progression will hold for more than a few elements on a diagonal. Using 41 produces one of the longest progressions.

    It is very easy to demonstrate that primes do follow a pattern that favors certain diagonals over others. Why that demonstration has eluded mathematicians and interested investigators since 1963 is what is amazing.

  2. lorg says:

    A. deAprix:
    When you say “no progression will hold” are you referring only to prime numbers, or any kind of progression?
    I think it’s the former, but it would be interesting if you meant otherwise. Also: “one of the longest progressions”: can we check that? What number will yield the longest progression?

  3. A. deAprix says:

    I am speaking of the progressions of primes. My concern with the spiral square has dealt with primes and prime loading. On the prime loading, I have been able to demonstrate that primes do favor certain diagonals; I did not attempt to find the longest possible progressions. From general scanning of the literature, I have seen it reported that starting with 41 does produce a long progression of primes on one diagonal, but I have not seen a longer one.

    Finding a longest known progression on a diagonal would be a variant of the problem that seeks to find the longest progression of primes with a given gap; the spiral square, however, has increasing gaps between the elements on a given diagonal, which would complicate the search.

  4. al deaprix says:

    If you want to see why some diagonals have more primes than others, see my article on http://www.scribd.com/al%20deaprix. I figured out the modularity of the system about 17-18 years ago, but never got around to doing much with it until recently. The proof that there is differential prime-loading on the diagonals is a very simple one, but one that has been overlooked by those seeking some more complicated answer.