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.

3736 35 34 33 3231

381716 15 141330

39 1854312 29

40 19 6 1 2 11 28

41 2078 9 10 27

42 21 22 23 24 25 26

4344 45 46 47 48 49It 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!