Project Euler Problem 58 Statement

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\%$?

Solution

Project Euler Problem 58 focuses on a square spiral that starts with the number 1 at the center and spirals outward in a counter-clockwise direction. For each layer added to the spiral (i.e., increasing the side length by 2), four new corner numbers are generated. The challenge is to determine the side length of the square spiral for which the ratio of prime numbers along both diagonals falls below a specified percentage N.

Let's have a look at the solution:

1. Initialization:

import Euler

N = int(input())
primes_count, slen, last_no, ratio = 0, 1, 1, 100

• Import Statement: The code imports our Euler module, which contains our Miller-Rabin primality test (is_prime_MR()).
• Input: The user provides an integer N representing the target percentage.
• Variables:
  • primes_count: Keeps track of the number of prime numbers found on the diagonals.
  • slen: Represents the current side length of the spiral.
  • last_no: The last number added to the spiral, initialized to 1 (the center of the spiral).
  • ratio: Monitor the ratio of prime numbers on the diagonals.

2. Main Loop & Termination:

while ratio >= N
    slen+= 2  # starting at 3
    for j in range(3):
        last_no+= slen - 1
        if Euler.is_prime_MR(last_no):
            primes_count+= 1
    last_no+= slen - 1  # Skip the fourth non-prime step
    ratio = primes_count / (1 + 2 * (slen - 1)) * 100

print(slen)

• Layer Processing:
  • For each new layer (increasing the side length by 2, slen+= 2), there are four new corner numbers. However, one of these corners is always a perfect square and hence not prime. To optimize, the code only checks the first three corners for primality.
  • The for j in range(3) loop iterates three times to calculate and check the first three corner numbers:
    • last_no+= slen - 1: Calculates the next corner number by adding slen - 1 to the previous number. This is because, in a square spiral, the difference between consecutive corners is consistent and equal to slen - 1.
    • Euler.is_prime_MR(last_no): Uses the Miller-Rabin primality test to check if the new corner number is prime. If it is, primes_count is incremented. Miller-Rabin is necessary given the potentially large numbers involved in the spiral.
• Ratio Calculation:
  • ratio = primes_count / (1 + 2*(slen-1)) * 100 < N: This calculates the current ratio of prime numbers on the diagonals. The total number of diagonal numbers for a spiral of side length slen is 1 + 2*(slen-1). If the prime ratio falls below the input percentage N, the loop exits, the current side length slen is printed, and the program terminates.
  • If the ratio condition isn't met, the side length is increased by 2 to analyze the next layer of the spiral.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 58

HackerRank Project Euler 58: What's the side length of the square spiral for which the ratio of primes along both diagonals first falls below $N%$, where $8\le N\le 60$?

Last Word

• The is_prime_MR function will be imported instead of hard coded into the source code. This provides flexibility to include different methods as required to solve a problem.