Project Euler Problem 58

Solution

Answer: 26241

The key to this problem is understanding how the numbers on the diagonals evolve as the spiral grows.

For a spiral of side length $n$ (where $n$ is odd), the outer layer contributes exactly four new corner numbers.

For example:

• Side length $1$: just $1$
• Side length $3$: corners are $3,5,7,9$
• Side length $5$: corners are $13,17,21,25$
• Side length $7$: corners are $31,37,43,49$

We need to track how many diagonal numbers are prime and determine when the ratio first falls below $10%$.

---

Mathematical analysis

1. Formula for the corner numbers

Consider a square spiral with odd side length $n$.

The largest number in the layer is always the bottom-right corner:

$$n^2$$

The step size between adjacent corners is:

$$n-1$$

So the four corners are:

$$\begin{aligned} c_1 &= n^2 \ c_2 &= n^2-(n-1) \ c_3 &= n^2-2(n-1) \ c_4 &= n^2-3(n-1) \end{aligned}$$

Example for $n=7$:

$$49,\ 43,\ 37,\ 31$$

which matches the diagram.

---

2. Number of diagonal entries

Each new layer adds 4 diagonal numbers.

For side length $n$:

$$\text{total diagonal numbers} = 2n-1$$

Check:

• $n=1$: $1$
• $n=3$: $5$
• $n=5$: $9$
• $n=7$: $13$

Correct.

---

3. Prime ratio

At each layer:

1. Generate the 4 corner numbers.
2. Test each for primality.
3. Update:

$$\text{ratio} = \frac{\text{prime diagonal count}} {\text{total diagonal count}}$$

We seek the first $n$ such that:

$$\frac{\text{primes}}{2n-1} < 0.10$$

---

Python implementation

import math

def is_prime(n):
    """Return True if n is prime, else False."""
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2

    limit = int(math.isqrt(n))
    d = 3

    while d <= limit:
        if n % d == 0:
            return False
        d += 2

    return True

prime_count = 0
diagonal_count = 1   # starts with center value 1
side_length = 1

while True:
    side_length += 2

    square = side_length * side_length
    step = side_length - 1

    # The four corner values
    corners = [
        square,
        square - step,
        square - 2 * step,
        square - 3 * step
    ]

    # Count primes among the corners
    for c in corners:
        if is_prime(c):
            prime_count += 1

    diagonal_count += 4

    # Check ratio
    if prime_count / diagonal_count < 0.10:
        print(side_length)
        break

---

Code walkthrough

Prime testing

def is_prime(n):

A standard efficient primality test.

• Reject numbers below 2.
• Handle even numbers separately.
• Test odd divisors up to:

$$\sqrt{n}$$

using:

math.isqrt(n)

which computes the integer square root efficiently.

---

Initial state

prime_count = 0
diagonal_count = 1
side_length = 1

Initially the spiral contains only:

$$1$$

which is not prime.

---

Expanding the spiral

side_length += 2

Spiral sizes are always odd:

$$1,3,5,7,\dots$$

---

Computing corners

square = side_length * side_length
step = side_length - 1

Then:

corners = [
    square,
    square - step,
    square - 2 * step,
    square - 3 * step
]

These are exactly the four corners of the new layer.

For $n=5$:

$$25,21,17,13$$

---

Updating counts

for c in corners:
    if is_prime(c):
        prime_count += 1

Count how many of the new diagonal numbers are prime.

Then:

diagonal_count += 4

because every layer contributes 4 new diagonal entries.

---

Checking the ratio

if prime_count / diagonal_count < 0.10:

Stop once the ratio first drops below $10%$.

---

Verification with the example

For side length $7$:

Diagonal numbers are:

$$1,3,5,7,9,13,17,21,25,31,37,43,49$$

Primes:

$$3,5,7,13,17,31,37,43$$

That is:

$$8 \text{ primes out of } 13$$

matching the problem statement.

---

Final verification

The ratio decreases gradually as layers grow because composite numbers become increasingly common among the corner values.

The known Project Euler result occurs at a moderately large odd side length, so we expect a value in the tens of thousands rather than something tiny.

Running the algorithm gives:

$$26241$$

which is odd, as required for a spiral side length.

---

Answer: 26241