Problem #58 is another example of a Project Euler problem where the process of Engineer’s Induction can be very useful. The question reads:
Project Euler Problem 58: Spiral primes
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%?
My solution for this problem definitely falls into the category of brute force. Here is my solution:
Solution #1: Engineer’s Induction and Brute Force Approach
We can notice by Engineer’s Induction that the four numbers on the diagonals in the (c-1)/2-th layer of the spiral have values c*c+c+1, c*c+2*c+2, c*c+3*c+3, and c*c+4*c+4. By checking whether each of these numbers is prime through the conventional method, the proportion of primes on the diagonals of the spiral can be determined. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Engineer's Induction Approach to Project Euler Problem #58
'''
import time
from math import sqrt
def isPrime(n):
if(n<=1):
return False
if(n<4):
return True
if(n%2==0):
return False
c = 3
while(c<=sqrt(n)):
if(n%c==0):
return False
c+=2
return True
def projectEulerProblemFiftyEight(p):
total = 5
found = 3
c = 3
while(found100>=totalp):
t = c*c+c+1
for a in range(3):
if isPrime(t):
found+=1
total+=1
t+=(c+1)
total+=1
c+=2
return c
start = time.time()
print projectEulerProblemFiftyEight(10)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
26241
--- 3.82181882858 seconds ---
for input of p = 10
'''
And with that, we’re done. This method took 3.8 seconds to run in Python 2.7. Looking back on it, it could be improved by 25% by noticing that c*c+4*c+4 is a perfect square for all integer values of c. There are probably many other ways to make this program more efficient, but unfortunately I am too lazy to look for them at this moment. I may come back to this problem eventually.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 