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 \approx 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\%\)?
Let \(n\) be the (odd) length of the square just after completing one full layer; then the new entries on the diagonals are in the four corners. The bottom-right corner has value \(n^2\), the bottom-left has value \(n^2 - n + 1\), the top-left has value \(n^2 - 2n + 2\), and the top-right has value \(n^2 - 3n + 3\). As a square, the first of these values cannot be prime, but the other three might be. My code keeps running tallies of how many diagonal entries have been seen and how many are prime, and breaks out when the ratio falls below \(10\%\).
from itertools import count
from sympy import isprime
def p58(target = 1/10):
a, b = 3, 5
for n in count(5, 2):
for p in [n**2-n+1, n**2-2*n+2, n**2-3*n+3]:
if isprime(p):
a += 1
b += 4
if a/b < target:
return n