Problem 58: Spiral Primes

Mathematical Development

Definition 1 (Ulam Spiral Layers). The spiral is organized into layers indexed by $k = 0, 1, 2, \ldots$, where layer $k = 0$ is the center (containing only the value 1) and layer $k \geq 1$ has side length $s_k = 2k + 1$.

Theorem 1 (Corner Values). For layer $k \geq 1$ (side length $s = 2k + 1$), the four diagonal corner values are:

Proof. The bottom-right corner of layer $k$ is the last number placed in that layer, namely $(2k+1)^2$. Moving counterclockwise along the outermost ring, consecutive corners are separated by $s - 1 = 2k$ positions. Thus, stepping back from $(2k+1)^2$:

$\square$

Lemma 1 (Bottom-Right Corner is Always Composite). For $k \geq 1$, $c_4(k) = (2k+1)^2$ is composite.

Proof. $(2k+1)^2$ has the nontrivial factor $2k + 1 \geq 3$, so it is a perfect square greater than 1, hence composite. $\square$

Theorem 2 (Diagonal Element and Prime Counts). After processing layers $1$ through $k$:

(i) The total number of diagonal elements is $T(k) = 4k + 1$ (including the center value 1).

(ii) The number of prime diagonal elements is

where $\mathbf{1}[\cdot]$ is the indicator function. The fourth corner $c_4(j)$ is excluded by Lemma 1.

Proof. (i) Layer 0 contributes 1 element. Each subsequent layer contributes 4 corners. After $k$ layers: $1 + 4k$. (ii) The center value 1 is not prime. At each layer $j$, at most 3 of the 4 corners can be prime (since $c_4$ is always composite). $\square$

Theorem 3 (The Ratio $P(k)/T(k) \to 0$). The prime ratio along the diagonals tends to zero as $k \to \infty$.

Proof. The corner values at layer $k$ are $\Theta(k^2)$. By the Prime Number Theorem, the probability that a random integer near $N$ is prime is asymptotically $1/\ln N$. For $N = \Theta(k^2)$, this probability is $\sim 1/(2 \ln k)$.

The expected number of primes contributed by layer $j$ is therefore approximately $3/(2 \ln j)$, and

by the integral estimate $\sum_{j=2}^{k} 1/\ln j \sim k/\ln k$ (a consequence of the prime number theorem applied to the sum). The ratio is

Corollary 1 (Existence of Threshold Crossing). For any $\varepsilon > 0$, there exists a finite $k_0$ such that $P(k_0)/T(k_0) < \varepsilon$. The problem asks for $s = 2k_0 + 1$ where $\varepsilon = 0.10$.

Lemma 2 (Primality Testing Bound). To test whether $n = c_i(k)$ is prime by trial division, it suffices to check divisors up to $\lfloor\sqrt{n}\rfloor \leq 2k + 1$.

Proof. If $n$ is composite, it has a factor at most $\sqrt{n}$. Since $c_i(k) \leq (2k+1)^2$, we have $\sqrt{c_i(k)} \leq 2k + 1$. $\square$

Proposition 1 (Rough Estimate via PNT). Setting $3/(8 \ln k) = 0.10$ gives $\ln k = 3.75$, hence $k \approx 42$, corresponding to side length $s \approx 85$. This is a very rough lower bound; the actual answer is much larger because the PNT approximation overestimates the prime count for small to moderate $k$.

Editorial

We process the spiral layer by layer. For each new side length $s = 2k+1$, only the three non-square corner values need to be tested for primality, because the fourth corner is always $(2k+1)^2$ and therefore composite. Maintaining the cumulative number of diagonal entries and diagonal primes allows the prime ratio to be updated after each layer, and the first side length for which this ratio falls below 10% is returned.

Pseudocode

Algorithm: Spiral Side Length at Which the Prime Ratio Falls Below One Tenth
Require: Primality testing for the diagonal corner values of the spiral.
Ensure: The first odd side length for which the ratio of prime numbers on the diagonals is less than 10%.
1: Initialize prime_count ← 0, diagonal_count ← 1, and k ← 0.
2: Repeat:
3:     Set k ← k + 1 and s ← 2k + 1, then form the three non-square corner values on the layer of side length s.
4:     Test those three corners for primality, update prime_count accordingly, and set diagonal_count ← diagonal_count + 4.
5:     If prime_count / diagonal_count < 0.1, return s.

Complexity Analysis

Theorem 4 (Time Complexity). Let $K$ denote the final layer index (so $s = 2K + 1$). With trial division, the algorithm runs in $O(K^2)$ time. With Miller-Rabin primality testing, the time reduces to $O(K \log^2 K)$.

Proof. At each layer $k$, we test 3 numbers for primality. Each corner value $n \leq (2K+1)^2$ has $\sqrt{n} = O(K)$. Trial division with the $6k \pm 1$ optimization tests $O(K/\ln K)$ candidates per number in the worst case, but the dominant cost across all $K$ layers is $\sum_{k=1}^{K} O(k) = O(K^2)$, since the trial division bound grows with $k$.

With deterministic Miller-Rabin using a fixed set of witnesses, each primality test costs $O(\log^2 n) = O(\log^2 K)$, giving total cost $3K \cdot O(\log^2 K) = O(K \log^2 K)$.

For the answer $K = 13120$ (side length $s = 26241$), $O(K^2) \approx 1.7 \times 10^8$, which is feasible. $\square$

Space: $O(1)$ — only a constant number of integer variables are maintained.

Answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// Modular multiplication using __int128 to avoid overflow.
ll mulmod(ll a, ll b, ll m) {
    return (__int128)a * b % m;
}

// Fast modular exponentiation: base^exp mod mod.
ll powmod(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = mulmod(result, base, mod);
        base = mulmod(base, base, mod);
        exp >>= 1;
    }
    return result;
}

// Single round of Miller-Rabin with witness a.
bool millerRabin(ll n, ll a) {
    if (n % a == 0) return n == a;
    ll d = n - 1;
    int r = 0;
    while (d % 2 == 0) { d /= 2; r++; }
    ll x = powmod(a, d, n);
    if (x == 1 || x == n - 1) return true;
    for (int i = 0; i < r - 1; i++) {
        x = mulmod(x, x, n);
        if (x == n - 1) return true;
    }
    return false;
}

// Deterministic primality test for n < 3.2 * 10^18.
bool isPrime(ll n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (ll a : {2, 3, 5, 7, 11, 13}) {
        if (!millerRabin(n, a)) return false;
    }
    return true;
}

int main() {
    int primeCount = 0;
    int totalDiag = 1;  // center = 1

    for (ll k = 1; ; k++) {
        ll s = 2 * k + 1;
        ll sq = s * s;
        totalDiag += 4;

        // Three non-square corners: skip (2k+1)^2 by Lemma 1
        if (isPrime(sq - (s - 1)))     primeCount++;
        if (isPrime(sq - 2 * (s - 1))) primeCount++;
        if (isPrime(sq - 3 * (s - 1))) primeCount++;

        if (primeCount > 0 && 10 * primeCount < totalDiag) {
            cout << s << endl;
            return 0;
        }
    }
    return 0;
}

"""
Project Euler Problem 58: Spiral Primes

What is the side length of the square spiral for which the ratio
of primes along both diagonals first falls below 10%?

Corner values at layer k (side length s = 2k+1):
  c1 = 4k^2 - 2k + 1,  c2 = 4k^2 + 1,  c3 = 4k^2 + 2k + 1
  c4 = (2k+1)^2  (always composite, skipped)

Answer: 26241
"""
from sympy import isprime

def solve():
    prime_count = 0
    total_diag = 1  # center = 1

    k = 0
    while True:
        k += 1
        s = 2 * k + 1
        sq = s * s
        total_diag += 4

        for corner in [sq - 2 * (s - 1), sq - (s - 1), sq - 3 * (s - 1)]:
            if isprime(corner):
                prime_count += 1

        if prime_count > 0 and prime_count / total_diag < 0.10:
            return s

if __name__ == "__main__":
    answer = solve()
assert answer == 26241
print(answer)