We encountered number spirals previously in problem 28, and now we revisit them in Problem 58. Here is the problem description.
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 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%?
We will take the same approach here as we did for solving problem 28. For each new square layer that is added, the numbers at the four corners will be of the form n2, n2 – (n-1), n2 – (n-1)*2, n2 – (n-1)*3. We will therefore check if each of these values (except, of course, n2) is prime and increment a counter accordingly.
My first attempt at solving this problem was using a prime sieve, but even with an upper limit of 100,000,000, we will be unable to reach 10%. So my revised attempt makes use of our trusty old is_prime() function.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
from euler_commons import is_prime prime_count = 0 i = 1 while True: i += 2 n1 = i ** 2 ## never prime n2 = n1 - (i - 1) n3 = n2 - (i - 1) n4 = n3 - (i - 1) for n in [n2, n3, n4]: if is_prime(n): prime_count += 1 prime_pct = prime_count / (2 * i - 1) if prime_pct < 0.1: break print(i) |