Detailed mathematical approach

Problem Summary

The tiles are numbered in hexagonal layers around the center tile 1. For each tile \(n\), \(PD(n)\) is the number of prime values among the six absolute differences between \(n\) and its six neighbors. The task is to find the 2000th tile for which \(PD(n)=3\).

The key point is that the successful implementations never build the whole spiral explicitly. They prove that, apart from the small exceptional tiles \(1\) and \(2\), every solution must be either the first tile or the last tile of some ring, and then they test only those two closed-form candidates per ring.

Mathematical Approach

Let ring \(k\) be the hexagonal layer at distance \(k\) from the center. Ring 0 consists only of tile 1, and ring \(k\ge 1\) contains \(6k\) tiles.

Ring Boundaries in Closed Form

After finishing ring \(k\), the total number of tiles is

$1+6(1+2+\cdots+k)=1+3k(k+1).$

Therefore the first and last tiles of ring \(k\) are

$A_k=3k(k-1)+2,\qquad B_k=3k(k+1)+1.$

So ring \(k\) is exactly the interval \([A_k,B_k]\), and its size is

$B_k-A_k+1=6k.$

These two endpoint formulas are the basic objects used everywhere in the solution.

Why Almost Every Tile Is Eliminated Immediately

Take a tile \(n\) in ring \(k\ge 2\) that is not one of the two endpoints \(A_k\) or \(B_k\). Its two neighbors on the same ring are then the consecutive values \(n-1\) and \(n+1\), so two of the six neighbor differences are already \(1\) and \(1\), which are not prime.

The other four neighbors lie on the adjacent inner and outer rings. Along a side of the spiral, those cross-ring differences appear in two consecutive pairs, and each such pair contains an even number. Hence among those four extra differences, at least two are even and greater than 2, so they are composite.

That means any non-endpoint tile can have at most two prime differences. Therefore, once the small cases are separated out, the only possible tiles with \(PD(n)=3\) are the two endpoints of each ring: the first tile \(A_k\) and the last tile \(B_k\).

The First Tile of a Ring

For \(k\ge 2\), the six neighbors of \(A_k\) can be written in terms of nearby ring endpoints:

$A_{k-1},\quad A_k+1,\quad B_k,\quad A_{k+1},\quad A_{k+1}+1,\quad B_{k+1}.$

Subtracting from \(A_k\) gives the six absolute differences

$1,\quad 6k-6,\quad 6k-1,\quad 6k,\quad 6k+1,\quad 12k+5.$

Among these, \(1\), \(6k-6\), and \(6k\) are automatically non-prime for \(k\ge 2\). So the condition collapses to exactly three numbers:

$PD(A_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+1),\ \operatorname{prime}(12k+5).$

The Last Tile of a Ring

For the other endpoint \(B_k\), the six neighbors are

$B_k-1,\quad A_k,\quad A_{k-1},\quad B_{k-1},\quad B_{k+1}-1,\quad B_{k+1}.$

This yields the six absolute differences

$1,\quad 6k-1,\quad 12k-7,\quad 6k,\quad 6k+5,\quad 6k+6.$

Again, \(1\), \(6k\), and \(6k+6\) are certainly composite for \(k\ge 2\). Hence

$PD(B_k)=3 \iff \operatorname{prime}(6k-1),\ \operatorname{prime}(6k+5),\ \operatorname{prime}(12k-7).$

At \(k=2\), the last two expressions are both 17, so the same prime gap occurs from two different neighbors. That still contributes two prime differences, which is exactly why \(B_2=19\) qualifies.

Worked Example: Ring \(k=2\)

The second ring starts at \(A_2=8\) and ends at \(B_2=19\).

For \(A_2=8\), the six differences are

$1,\ 6,\ 11,\ 12,\ 13,\ 29,$

so the prime ones are \(11,13,29\), and therefore \(PD(8)=3\).

For \(B_2=19\), the six differences are

$1,\ 11,\ 12,\ 17,\ 17,\ 18,$

so the prime differences are \(11,17,17\), again giving \(PD(19)=3\).

This matches the beginning of the sequence generated by the implementations:

$1,\ 2,\ 8,\ 19,\ 20,\ 37,\dots$

Sequence Generation Criterion

The center tile satisfies \(PD(1)=3\), and tile 2 is the other exceptional small case. After that, the entire search becomes a scan over \(k=2,3,4,\dots\) with only two tests per ring.

The first endpoint \(A_k\) is accepted when

$6k-1,\ 6k+1,\ 12k+5$

are all prime, in which case the tile number is

$A_k=3k(k-1)+2.$

The last endpoint \(B_k\) is accepted when

$6k-1,\ 6k+5,\ 12k-7$

are all prime, in which case the tile number is

$B_k=3k(k+1)+1.$

That is the whole mathematical reduction embodied in the code.

How the Code Works

The C++, Python, and Java implementations begin by storing the first two valid tiles, \(1\) and \(2\). They then iterate over ring indices \(k\ge 2\). No coordinate grid, adjacency table, or spiral simulation is built, because the derivation above has already reduced the problem to two explicit candidates per ring.

For each ring, the implementation first forms \(6k-1\), which appears in both endpoint tests. It then checks the three-prime condition for the first endpoint and, if successful, records \(3k(k-1)+2\). After that it checks the three-prime condition for the last endpoint and, if successful, records \(3k(k+1)+1\).

The three language versions differ only in their primality routine. The C++ implementation uses modular multiplication together with a deterministic Miller-Rabin test for 64-bit inputs, the Java implementation uses trial division through numbers of the form \(6m\pm1\), and the Python implementation delegates primality testing to a library predicate. All three apply the same formulas and stop as soon as the requested index is reached.

Complexity Analysis

If the search reaches ring \(K\), the algorithm examines exactly two candidate tiles per ring and performs only constant-time arithmetic around them. Candidate generation is therefore \(O(K)\).

The full running time is \(O(K\cdot P(K))\), where \(P(K)\) is the cost of one primality test on numbers of size \(O(K)\). With trial division this is \(O(K\sqrt{K})\); with deterministic Miller-Rabin on 64-bit integers, primality testing is effectively constant-time at this scale. In practice the search is very small for the Project Euler target.

The implementations keep the successful tiles found so far in a list or array, so the auxiliary space is \(O(T)\) for target index \(T\). For \(T=2000\), this is negligible.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=128
2. Hexagonal tiling: Wikipedia - Hexagonal tiling
3. Centered hexagonal number: Wikipedia - Centered hexagonal number
4. Prime number: Wikipedia - Prime number
5. Primality test: Wikipedia - Primality test