## Project Euler 58: Counting primes that lie on the diagonals of the spiral grid

#### Problem Description

Starting with 1 and spiralling counterclockwise 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%?

#### Analysis

Forget about the geometry and determine the series instead: (3, 5, 7, 9), (13, 17, 21, 25), (31, 37, 43, 49), … This represents the “corners” for every square layer.

Determine and count the primes, *p _{n}*, in the series ignoring every 4th one since it will always be a square and therefore composite. As soon as we reach a ratio of primes to series length (

*n*),

*p*/

_{n}*n*< 10% we can calculate a side length as

*n*/2.

It’s important to have a decent *is_prime()* function to achieve a better run time.

#### Project Euler 58 Solution

Runs < 0.500 seconds in Python 2.7.```
from Euler import miller_rabin as m_r
n_prime, d, avg, n = 0, 1, 1, 2
while avg >= 0.10:
n_prime += m_r(d + n) + m_r(d + n*2) + m_r(d + n*3)
d += n*4
n += 2
avg = n_prime / (2.0 * n) # the decimal forces a float calculation
print "Project Euler 58 Solution =", n-1
```

Use this link to get the Project Euler 58 Solution Python 2.7 source.#### Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose*define*to reveal the answer.

#### Afterthoughts

- Function
`miller_rabin`

is listed in Common Functions and Routines for Project Euler - Using the Miller-Rabin primality test,
`miller_rabin`

, in place of`is_prime`

sped things up 3 fold. We are using the default accuracy of 5 which is low but fast. - Note how we calculate the answer as n-1. This is because we count only even n and the side length of our layer has to be odd.
- See also, Project Euler 28 Solution: Find the sum of both diagonals in a square spiral.

*Project Euler 58 Solution last updated*

It is fun to note that this solution provides incorrect answers around bound<=0.0895. This is because the floating point error on the ratio is enough by then to push us just under the limit one iteration too soon. If we re-compute n from the precise integrals we seem to last longer, but it is still a matter of time before that result differs from a result using exact rational values.