Project Euler 58 : The Ulam Spiral

Alrighty! Back to Project Euler after a really long time and the difference is pretty noticeable, both in PE as well as my thinking.

PE’s got a new interface and an awesome new badge system for would-be Eulerians. However the cooler thing is that I was able to solve a problem that initially gave me many a sleepless night.

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37   36   35   34   33   32   31
38   17   16   15   14   13  30
39   18     5    4     3   12  29
40   19     6    1     2   11  28
41   20    7     8    9   10   27
42   21   22   23  24   25   26
43  44   45   46  47   48   49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13  62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Pretty harrowing at first glance, but the solution is really straightforward. 🙂

This spiral is nothing but the Ulam Spiral and it has some interesting properties. Notice the left-down diagonal has all squares? The square value is simply twice the spiral layer plus 1 squared. So the first layer i.e. 1 gives (2*1 + 1)^2 = 9. Then the other 4 values are obtained by subtracting the previous even number’s 3 multiples from the square.

E.g. Take 49. That is the square of 7, 6 is the even number before it. So to get the other diagonal elements, all I do is 49 – 6, = 43, 49 – 12 = 37 and 49 – 18 = 31. This simple pattern works all the time for every layer, feel free to check!

Now, the code to solve this is even simpler. C++ can do this, but finding the range of prime numbers is a big hassle and I couldn’t find a good enough upper bound to apply The Sieve without getting a Segmentation fault, and too large values just can’t be accommodated.

Thankfully, I learnt Python this last semester while doing the coursework of an online Robotics class by Prof. Thrun. So, I decided to write a terse program to achieve the solution. Here it is:

from math import *

def isprime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    for x in range(3, int(n**0.5)+1):
       if n % x == 0:
           return False

    return True;

def calculate():
    primes = 3
    count = 5
    layer = 1

    while float(primes)/count >= 0.1:
        layer += 1
        m = 2*layer + 1

        for i in range(4):
            if isprime(m*m - i*(m-1)):
                primes += 1
            count += 1

    return 2*layer + 1

print calculate()

So I hope you understand what I am trying to do. The code is short and sweet and pretty self-explanatory, except, for the sake of the while loop, I am starting from the first layer rather than the zeroth layer which only has 1.  Now I better get back to my other programs!

Eviva!