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 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:
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'.
Tags: Math, prime numbers, Programming, Python, Ulam spiral
October 16th, 2009 at 1:45 pm
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.
October 18th, 2009 at 12:32 am
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?
October 19th, 2009 at 1:06 pm
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.
November 12th, 2009 at 10:47 am
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.