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!