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