// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (10 votes, average: 4.60 out of 5)
Loading...

Project Euler Solutions

Project Euler 58 Solution

Project Euler 58 Solution

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, pn, 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), pn/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
download arrowUse 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.
|26241|

Afterthoughts

Project Euler 58 Solution last updated

Discussion

One Response to “Project Euler 58 Solution”

  1. 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.

    Posted by Thomas DuBuisson | December 9, 2015, 9:40 PM

Post a comment