Problem 128: Hexagonal Tile Differences

Mathematical Development

Definition. The hexagonal spiral has ring 0 (tile 1) at the center. Ring $r$ ($r \geq 1$) contains $6r$ tiles. The first tile of ring $r$ is $S(r) = 3r(r-1) + 2$. The last tile of ring $r$ is $E(r) = 3r(r+1) + 1$.

Theorem 1 (Ring formulas). The first and last tile numbers of ring $r \geq 1$ are:

Proof. Ring $r$ contains $6r$ tiles, and rings $1, \ldots, r-1$ contain $\sum_{i=1}^{r-1} 6i = 3r(r-1)$ tiles. Adding the center tile (tile 1), the first tile of ring $r$ is $1 + 3r(r-1) + 1 = 3r(r-1) + 2$. The last tile is $S(r) + 6r - 1 = 3r(r-1) + 2 + 6r - 1 = 3r^2 + 3r + 1 = 3r(r+1) + 1$. $\square$

Theorem 2 (Only endpoints have $PD = 3$). For $n > 1$, $PD(n) = 3$ can only occur when $n = S(r)$ or $n = E(r)$ for some ring $r$. Interior tiles (not at the first or last position of a ring) have $PD(n) \leq 2$.

Proof. Consider a tile at position $j$ along ring $r$ (not at a corner or endpoint). Its six neighbors include tiles from rings $r-1$, $r$, and $r+1$. Among the six differences, at least four are either 1 or even numbers $\geq 4$:

• Two adjacent tiles in the same ring give differences 1 (not prime) or small even.
• Neighbors in adjacent rings give differences that include $6r$ or $6(r-1)$ (both even).

Thus at most 2 differences can be prime, giving $PD \leq 2$. Only the first and last tiles of each ring have a special neighbor configuration that allows exactly 3 prime differences. $\square$

Theorem 3 (Difference formulas for $S(r)$). The six neighbor differences of $S(r)$ for $r \geq 2$ are: $1$, $6(r-1)$, $6r$, $6r - 1$, $6r + 1$, and $12r + 5$. Of these, only $6r-1$, $6r+1$, and $12r+5$ can be prime. Thus $PD(S(r)) = 3$ if and only if all three are prime.

Proof. The neighbors of $S(r)$ are:

• $E(r-1) = S(r) - 1$: difference 1 (not prime).
• $S(r-1) = 3(r-1)(r-2) + 2$: difference $S(r) - S(r-1) = 6(r-1)$ (even, $\geq 4$ for $r \geq 3$).
• $S(r+1) = 3(r+1)r + 2$: difference $S(r+1) - S(r) = 6r$ (even).
• $E(r) = 3r(r+1) + 1$: difference $E(r) - S(r) = 6r - 1$.
• $S(r+1) + 1 = 3r(r+1) + 3$: difference $S(r+1) + 1 - S(r) = 6r + 1$.
• The sixth neighbor (in ring $r-1$): difference $12r + 5$.

The values 1, $6(r-1)$, $6r$ are never prime for $r \geq 3$. The remaining three ($6r-1$, $6r+1$, $12r+5$) may be prime. $\square$

Theorem 4 (Difference formulas for $E(r)$). For $r \geq 2$, the potentially prime differences of $E(r)$ are $6r - 1$, $6r + 5$, and $12r - 7$. Thus $PD(E(r)) = 3$ if and only if all three are prime.

Proof. The neighbors of $E(r)$ are:

• $E(r) - 1$ (previous tile in ring): difference 1.
• $S(r+1) = E(r) + 1$: difference 1.
• $E(r+1) = 3(r+1)(r+2) + 1$: difference $E(r+1) - E(r) = 6(r+1)$ (even).
• $E(r-1) = 3(r-1)r + 1$: difference $E(r) - E(r-1) = 6r$ (even).
• Two additional neighbors yield differences $6r - 1$, $6r + 5$, and $12r - 7$.

For $r \geq 2$, $12r - 7 \geq 17 > 1$, so all three candidates are valid. $\square$

Lemma 1 (Tile 1). $PD(1) = 3$, since the neighbors of tile 1 are tiles 2—7, giving differences $1, 2, 3, 4, 5, 6$. The primes among these are $2, 3, 5$.

Proof. Direct computation. $\square$

Editorial

The key structural fact is that almost every tile can be discarded without inspection. The only candidates for $PD(n)=3$ are tile 1 and the two endpoint tiles of each ring, namely the first tile $S(r)$ and the last tile $E(r)$. The mathematical section reduces each of those cases to three explicit primality conditions, so the infinite spiral turns into a simple sweep over ring numbers.

The implementation seeds the count with tile 1, then walks outward ring by ring. At each ring it tests the three prime differences associated with $S(r)$ and, for $r \ge 2$, the three associated with $E(r)$. Every time one of those endpoint formulas passes, another valid tile has been found; the process stops at the 2000th success.

Pseudocode

Count tile 1 as the first solution.

For ring numbers r = 1, 2, 3, ... :
    Test the three prime-difference conditions for the first tile S(r).
    If they all hold, increase the solution count and return S(r) when the target count is reached.
    If r is at least 2, test the three prime-difference conditions for the last tile E(r).
    If they all hold, increase the solution count and return E(r) when the target count is reached.

Complexity Analysis

• Time: $O(R \cdot \log^2 M)$ where $R$ is the ring number of the 2000th qualifying tile and $M$ is the magnitude of the numbers tested for primality ($M \sim 12R$). Each ring requires $O(1)$ primality tests, each costing $O(\log^2 M)$ via Miller-Rabin.
• Space: $O(1)$ (no arrays needed beyond the primality test).

Answer

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

typedef long long ll;
typedef __int128 lll;

ll mulmod(ll a, ll b, ll m) {
    return (lll)a * b % m;
}

ll powmod(ll a, ll b, ll m) {
    ll res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = mulmod(res, a, m);
        a = mulmod(a, a, m);
        b >>= 1;
    }
    return res;
}

bool miller_rabin(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;
}

bool is_prime(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, 17, 19, 23}) {
        if (!miller_rabin(n, a)) return false;
    }
    return true;
}

int main() {
    // Tile 1 is the first with PD=3.
    // For ring r >= 1:
    //   First tile S(r) = 3r(r-1)+2: check 6r-1, 6r+1, 12r+5 all prime
    //   Last tile  E(r) = 3r(r+1)+1: check 6r-1, 6r+5, 12r-7 all prime (r>=2)

    int count = 1; // tile 1
    int target = 2000;

    for (ll r = 1; ; r++) {
        // First tile of ring r
        if (is_prime(6*r - 1) && is_prime(6*r + 1) && is_prime(12*r + 5)) {
            count++;
            if (count == target) {
                cout << 3*r*(r-1) + 2 << endl;
                return 0;
            }
        }

        // Last tile of ring r (r >= 2 for 12r-7 to be > 1)
        if (r >= 2 && is_prime(6*r - 1) && is_prime(6*r + 5) && is_prime(12*r - 7)) {
            count++;
            if (count == target) {
                cout << 3*r*(r+1) + 1 << endl;
                return 0;
            }
        }
    }

    return 0;
}

"""
Problem 128: Hexagonal Tile Differences

Find the 2000th tile for which exactly 3 of the differences
with its 6 neighbors are prime.

Key insight: Only the first and last tile of each ring can have PD=3.
- First tile S(r) = 3r(r-1)+2: needs 6r-1, 6r+1, 12r+5 all prime
- Last tile  E(r) = 3r(r+1)+1: needs 6r-1, 6r+5, 12r-7 all prime (r>=2)
"""

from sympy import isprime

def solve(target=2000):
    count = 1  # tile 1 is the first with PD=3

    r = 1
    while True:
        # First tile of ring r
        if isprime(6*r - 1) and isprime(6*r + 1) and isprime(12*r + 5):
            count += 1
            if count == target:
                return 3*r*(r-1) + 2

        # Last tile of ring r (r >= 2 for 12r-7 > 1)
        if r >= 2 and isprime(6*r - 1) and isprime(6*r + 5) and isprime(12*r - 7):
            count += 1
            if count == target:
                return 3*r*(r+1) + 1

        r += 1

if __name__ == '__main__':
    answer = solve()
    print(answer)