Categories

## 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:

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’.