Problem 128: Hexagonal Tile Differences

Project Euler Problem 128 Solution

EulerSolve provides an optimized solution for Project Euler Problem 128, Hexagonal Tile Differences, with C++, Python, Java, and a step-by-step mathematical explanation.

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$....

Detailed mathematical approach

Problem Summary

Hexagonal tiles are laid in rings around a central tile with the number $1$. The first ring consists of the six tiles $2$ to $7$, numbered anticlockwise starting with the tile at 12 o'clock, directly above tile $1$, and every further ring is numbered in the same way from its own tile at 12 o'clock: the next rings hold the tiles $8$ to $19$, $20$ to $37$, $38$ to $61$, and so on. For a tile $n$, $\operatorname{PD}(n)$ is the number of its six neighbours $m$ for which the difference $|n-m|$ is a prime; equal prime differences count separately. Going clockwise around tile $8$ the differences are $12, 29, 11, 6, 1, 13$, so $\operatorname{PD}(8)=3$; around tile $17$ they are $1, 17, 16, 1, 11, 10$, so $\operatorname{PD}(17)=2$. The statement notes that $\operatorname{PD}(n)$ never exceeds $3$ and that the $10$th tile with $\operatorname{PD}(n)=3$, in increasing order, is $271$. We must find the $2000$th tile of this list. ^[1]

The whole solution in one sentence: apart from the tiles $1$ and $2$, only the first and the last tile of a ring can have three prime differences, and for these two tiles the six differences are simple expressions in the number $k$ of the ring, so we go through the rings $k=2,3,\dots$ and, for each of the two tiles, test whether three numbers are prime.

Mathematical Approach

We first work out where every number lies and which numbers are neighbours. A parity argument then rules out all but two tiles in each ring, and for those two $\operatorname{PD}(n)=3$ becomes a test of three numbers.

1. Steps, rings and their first and last tiles

Let $e_0,e_1,\dots,e_5$ be the six steps from a tile to its neighbours, numbered anticlockwise and starting with the step upwards; indices are counted modulo $6$, so $e_6=e_0$. Steps can be added like arrows, so every tile has a position, the sum of the steps that lead to it from tile $1$. ^[2] Two facts about the hexagonal grid are all we need: opposite steps cancel, $e_{j+3}=-e_j$, and the two steps next to a direction add up to it, $e_{j-1}+e_{j+1}=e_j$. For instance, a step to the upper right followed by a step to the upper left ends directly above the start.

Tile $1$ forms ring $0$, and ring $k\ge1$ consists of the tiles $k$ steps away from it. Its numbering starts at the tile at $k\,e_0$, at 12 o'clock, and walks anticlockwise: $k$ steps $e_2$, then $k$ steps each of $e_3$, $e_4$, $e_5$, $e_0$ and $e_1$. The last of these $6k$ steps returns to the start, so the ring has $6k$ tiles, for example the $12$ tiles $8$ to $19$ of ring $2$. Rings $0$ to $k$ together contain $1+6(1+2+\dots+k)=3k(k+1)+1$ tiles, the centred hexagonal numbers $1, 7, 19, 37, 61,\dots$. ^[3] Ring $k$ therefore runs from its first tile $A_k$ to its last tile $B_k$, where

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

For example $A_2=8$, $B_2=19$, $A_3=20$ and $B_3=37$. Two consequences are used often: $A_{k+1}-A_k=6k$, the size of ring $k$, and $B_k=A_k+6k-1$.

2. Corners and sides

Because $e_j+e_{j+2}=e_{j+1}$, the $k$ steps $e_{j+2}$ lead from the point $k\,e_j$ to the point $k\,e_{j+1}$. These six points are the corners of ring $k$, and the stretch from corner $j$ up to the tile before corner $j+1$ is side $j$. Counting along the walk, the tile $i$ of side $j$, with $0\le i\le k-1$, has the number $n$ and the position $P$ given by

$$n=A_k+jk+i,\qquad P=k\,e_j+i\,e_{j+2}.$$

For ring $2$ the corners are $8, 10, 12, 14, 16, 18$, and side $4$ consists of $16$ and $17$. The last tile $B_k=A_k+5k+(k-1)$ is the tile $i=k-1$ of side $5$; it lies next to the first tile $A_k$, where the walk closes.

3. The neighbours of a tile

The six neighbours of the tile at $P$ are $P\pm e_j$, $P\pm e_{j+1}$ and $P\pm e_{j+2}$. Rewriting them in the form of Section 2 with $e_{j+1}=e_j+e_{j+2}$ gives their numbers. Take first a tile with $1\le i\le k-1$ in a ring $k\ge2$, so not a corner, other than the last tile $B_k$:

$P\pm e_{j+2}$ are the tiles $i\pm1$ of the same side, with the numbers $n\pm1$; for $i=k-1$ the tile $i+1$ is the next corner, which still has the number $n+1$;
$P+e_j=(k+1)e_j+i\,e_{j+2}$ and $P+e_{j+1}=(k+1)e_j+(i+1)e_{j+2}$ are the tiles $i$ and $i+1$ of side $j$ in ring $k+1$. Their numbers are $A_{k+1}+j(k+1)+i$ and one more, so by $A_{k+1}-A_k=6k$ they differ from $n$ by $6k+j$ and $6k+j+1$;
$P-e_j=(k-1)e_j+i\,e_{j+2}$ and $P-e_{j+1}=(k-1)e_j+(i-1)e_{j+2}$ are the tiles $i$ and $i-1$ of side $j$ in ring $k-1$, at the differences $6k-6+j$ and $6k-5+j$. For $i=k-1$, the tile $i$ of that side is the next corner of ring $k-1$, whose number follows the same formula.

The tile $B_k$ is left out because the numbering jumps back there: on side $5$ the corner after the last tile is not $B_k+1$ but the first tile $A_k$, and the corner after the last tile of ring $k-1$ is $A_{k-1}$; Section 6 deals with it. A corner $n=A_k+jk$ with $1\le j\le5$, at $P=k\,e_j$, is different. On its ring it touches the tile $n+1$ at $P+e_{j+2}$ and the tile $n-1$, the last of side $j-1$, at $P-e_{j+1}$. Outside it touches the corner $P+e_j$ of ring $k+1$ and the tiles on both sides of that corner, $P+e_{j+1}$ and $P+e_{j-1}$, at the differences $6k+j$, $6k+j+1$ and $6k+j-1$. Inside it touches only the corner $P-e_j$ of ring $k-1$, at the difference $6k-6+j$.

Two examples. Tile $17=A_2+4\cdot2+1$ is the tile $i=1$ of side $4$ in ring $2$; its differences $1, 1, 16, 17, 10, 11$, to the tiles $16$, $18$, $33$, $34$, $7$ and $6$, are those of the statement. The corner $10=A_2+2$ has the neighbours $9$, $11$, $23$, $24$, $22$ and $3$, at the differences $1, 1, 13, 14, 12, 7$.

4. Two even differences

Claim. If $k\ge2$ and $n$ is a tile of ring $k$ other than $A_k$ and $B_k$, then $\operatorname{PD}(n)\le2$.

Proof. Two of the six differences equal $1$, which is not a prime. For a side tile the other four are $6k-6+j$, $6k-5+j$, $6k+j$ and $6k+j+1$: two pairs of consecutive numbers, each with one even member. For a corner they are $6k-6+j$, $6k+j-1$, $6k+j$ and $6k+j+1$; here $6k-6+j$ and $6k+j$ differ by $6$ and have the same parity, and $6k+j\pm1$ have the other one. In both cases exactly two of the four numbers are even, and they are at least $6k-6\ge6$. The only even prime is $2$, so at most two differences are prime.

For example, tile $10$ has the even differences $12$ and $14$, and $\operatorname{PD}(10)=2$ counts the primes $7$ and $13$. The argument breaks down at $A_k$ and $B_k$, where the jumps in the numbering replace some differences by numbers of the other parity.

5. The first tile of a ring

The first tile $A_k$, at $k\,e_0$, is corner $0$. For $k\ge2$ the corner rule of Section 3 applies, except that the tiles before corner $0$ in rings $k$ and $k+1$ are the last tiles $B_k$ and $B_{k+1}$ of these rings. So the neighbours of $A_k$ are $A_k+1$, $B_k$, $A_{k-1}$, $A_{k+1}$, $A_{k+1}+1$ and $B_{k+1}$, and since $B_{k+1}-A_k=12k+5$, its differences are

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

The numbers $1$, $6k-6$ and $6k$ are not prime, so $\operatorname{PD}(A_k)=3$ exactly when $6k-1$, $6k+1$ and $12k+5$ are all prime. For $k=2$ the differences of tile $8$ are $1, 11, 6, 12, 13, 29$, the six numbers of the statement in a different order, and $11$, $13$ and $29$ are prime.

6. The last tile of a ring

The last tile $B_k$ is the tile $i=k-1$ of side $5$, and both jumps of Section 3 concern it: its successor on the ring is $A_k$, and its inner neighbour at $P-e_5$ is the first tile $A_{k-1}$ of ring $k-1$. Its six neighbours are $B_k-1$, $A_k$, $B_{k-1}$, $A_{k-1}$, $B_{k+1}-1$ and $B_{k+1}$, at the differences

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

The numbers $1$, $6k$ and $6k+6$ are not prime, so $\operatorname{PD}(B_k)=3$ exactly when $6k-1$, $6k+5$ and $12k-7$ are all prime. For $k=2$, tile $19$ has the neighbours $18, 8, 7, 2, 36, 37$ and the differences $1, 11, 12, 17, 17, 18$. The prime $17$ appears twice, as the difference from tile $2$ and from tile $36$, and both count, so $\operatorname{PD}(19)=3$.

7. The centre and the first ring

Sections 3 to 6 assume $k\ge2$. In ring $1$ every tile is a corner and touches tile $1$, and the differences from tile $1$ include the primes $2$, $3$ and $5$, so these seven tiles are checked directly. Tile $1$ has the differences $1$ to $6$, so $\operatorname{PD}(1)=3$, and tile $2$, with the neighbours $1, 3, 7, 8, 9, 19$ and the differences $1, 1, 5, 6, 7, 17$, has $\operatorname{PD}(2)=3$. Tiles $3$, $4$, $6$ and $7$ have two prime differences and tile $5$ has none. The test of Section 6 would wrongly accept $7=B_1$, because $5$, $11$ and $5$ are prime; but tile $7$ is a corner, and its neighbours $1, 2, 6, 17, 18, 19$ give only the primes $5$ and $11$. This is why the search starts at ring $2$, with the tiles $1$ and $2$ already in the list.

8. The largest value of PD

The statement's remark that $\operatorname{PD}(n)$ never exceeds $3$ now follows: in rings $k\ge2$ other tiles have at most two prime differences by Section 4, $A_k$ and $B_k$ have the three non-prime differences $1$ and two even numbers of at least $6$, and Section 7 covers rings $0$ and $1$.

9. Worked example: the first ten tiles

Since $A_k\lt B_k\lt A_{k+1}$, testing $A_k$ and then $B_k$ for $k=2,3,\dots$ produces the tiles in increasing order. The first rings give:

$k=2$: $11, 13, 29$ and $11, 17, 17$ are all prime, so $8$ and $19$ qualify;
$k=3$: $17, 19, 41$ and $17, 23, 29$ are all prime: $20$ and $37$;
$k=4$: $25$ is not prime, but $23, 29, 41$ are: only $61$;
$k=5$: $65$ and $35$ are not prime: neither tile;
$k=6$: $6k-1=35$ is not prime, which rules out both tiles;
$k=7$: $41, 43, 89$ are prime, $77$ is not: only $128$;
$k=8$: $49$ is not prime, $47, 53, 89$ are: only $217$;
$k=9$: $55$ is not prime, $53, 59, 101$ are: only $271$.

Together with $1$ and $2$ this gives $1, 2, 8, 19, 20,$ $37, 61, 128, 217, 271$, and the $10$th tile is $271$, as the statement says.

10. How rare the tiles are

Small primes rule out whole families of rings. Two integers are congruent modulo $5$ when their difference is a multiple of $5$, ^[4] and $6k-1$, $6k+1$ and $12k+5$ are congruent to $k-1$, $k+1$ and $2k$; for $k\ge2$ they exceed $5$, so none may be a multiple of $5$, and a first tile needs $k\equiv2$ or $3\pmod5$. Likewise $6k+5\equiv k$ and $12k-7\equiv2(k-1)$ leave $k\equiv2,3,4$ for a last tile. Apart from $1$ and $2$, the first $1000$ tiles of the list are $426$ first and $572$ last tiles. A first tile needs the twin primes $6k-1$ and $6k+1$, and whether there are infinitely many twin primes is a famous open problem. ^[5]

How the Code Works

The C++ program ^[6] reads two optional arguments in parse_arguments: --target= with the position in the list (default $2000$) and --skip-checkpoints. Unless the second one is given, run_checkpoints first confirms that solve(10) returns the statement's value $271$, and the program stops with exit code $2$ if it does not. solve(target) returns $1$ and $2$ directly for the first two positions; otherwise it starts the vector values with these two tiles (Section 7) and loops over $k=2,3,\dots$. In each ring it appends $3k(k-1)+2$ if $6k-1$, $6k+1$ and $12k+5$ are prime (Section 5), then $3k(k+1)+1$ if $6k-1$, $6k+5$ and $12k-7$ are prime (Section 6), and it stops as soon as the vector holds target tiles. By Section 9 the vector is sorted, so values[target-1] is the requested tile. Each test chains its three calls with &&, which stops at the first false part.

is_prime divides by the twelve primes from $2$ to $37$ and then runs the Miller–Rabin test: with $n-1=2^sd$ and $d$ odd, $n$ passes for a base $a$ if $a^d\equiv1$ or $a^{2^rd}\equiv-1\pmod n$ for some $0\le r\lt s$. A prime always passes: by Fermat's little theorem the chain of squares $a^d,a^{2d},\dots,a^{2^sd}$ ends with $1$, and modulo a prime $1$ has only the square roots $\pm1$, so the first $1$ is $a^d$ or follows a $-1$. No composite $n\lt341\,550\,071\,728\,321$ passes for all seven bases $2, 3, 5, 7, 11, 13, 17$ used here. ^[7] pow_mod computes the powers by repeated squaring, and mul_mod multiplies in the 128-bit type unsigned __int128, so no product overflows.

The Python function solve fixes target at $2000$, starts the list values with $1$ and $2$ and runs the same loop with sympy.isprime, whose answer is definitive below $2^{64}$; ^[8] it has no checkpoint. The Java main also fixes target at $2000$ and fills a preallocated long array, with cnt counting its entries from $2$; it tests primality by trial division in isPrime: after $2$ and $3$ it tries only $p$ and $p+2$ for $p=5, 11, 17,\dots$ while $p^2\le n$, that is, the numbers $6m\pm1$, since every prime above $3$ has this form. ^[9] The tiles grow like $3k^2$ and outgrow signed 32-bit integers: already the $1000$th tile, $2415336751$, exceeds $2^{31}-1$. C++ therefore uses u64 (std::uint64_t), Java long, and Python's integers have no fixed size.

Complexity and Verification

If the search ends in ring $K$, it makes between two and six primality tests per ring, on numbers of at most $12K+5$: exactly two, both on $6k-1$, whenever $6k-1$ is composite, which is the case in about three quarters of the rings. Counting arithmetic on 64-bit numbers as single steps, one Miller–Rabin test costs $O(\log n)$ multiplications per base, so the C++ program needs $O(K\log K)$ time, while the Java trial division costs up to $O(\sqrt n)$ divisions per test and $O(K\sqrt K)$ in total. SymPy also uses deterministic Miller–Rabin tests for such numbers, ^[8] so Python has the same order of cost; all three store only the $O(T)$ tiles found for the $T$th one. For the $10$th tile the loop stops in ring $9$ after $40$ primality tests, for the $100$th in ring $773$ after $2403$ tests, and for the $1000$th in ring $28374$ after $76068$ tests, none of them on a number larger than $340481$. For the $2000$th tile it needs fewer than $2\cdot10^5$ tests, all on numbers below $10^6$, and each of the three programs finishes in well under a second on a desktop computer.

The C++ program checks the statement's $10$th tile first. For this article, a separate program built the spiral from the steps of Section 1 and counted the prime differences of all $3003001$ tiles in rings $0$ to $1000$ directly: it reproduces the statement's examples, confirms the formulas of Sections 3, 5 and 6 for every tile of rings $2$ to $1000$, and finds no $\operatorname{PD}(n)\gt3$ and exactly the $119$ tiles that the tests produce. A second program, which computes the number of a tile from its position, finds the neighbours of $A_k$ and $B_k$ geometrically in every ring up to the end of the search for the $2000$th tile, agrees there with the three-number tests and with the published programs, and finds at most two prime differences for $20000$ random other tiles in rings up to $200000$. All three published programs print the same tile. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The neighbour formulas, the parity argument and the two three-number tests are derived explicitly in this article.

Project Euler 128 — Hexagonal Tile Differences. The official statement numbers hexagonal tiles in rings around tile 1, anticlockwise from 12 o'clock, defines PD(n), gives PD(8) = 3 and PD(17) = 2, states that PD(n) is at most 3 and that the 10th tile with PD(n) = 3 is 271, and asks for the 2000th such tile.
Amit J. Patel, Red Blob Games — Hexagonal Grids. In cube and axial coordinates steps to neighbours add like vectors; a ring of radius k is walked with k steps along each of six directions and has 6k hexes.
Wikipedia — Centered hexagonal number. The n-th centred hexagonal number 3n(n − 1) + 1 counts a centre dot and the dots around it in a hexagonal lattice: 1, 7, 19, 37, 61, …; with n = k + 1 it is the number of tiles in rings 0 to k.
Wikipedia — Modular arithmetic. Integers are congruent modulo m when their difference is a multiple of m; congruence is compatible with addition, subtraction and multiplication.
Wikipedia — Twin prime. Every twin prime pair greater than (3, 5) has the form (6n − 1, 6n + 1), and it is unknown whether there are infinitely many twin primes.
C++ — Euler128.cpp. The linked immutable C++ revision contains is_prime, solve and run_checkpoints. It is the implementation record for this article.
Wikipedia — Miller–Rabin primality test. With n − 1 = 2ˢd and d odd, n is a strong probable prime to the base a if aᵈ ≡ 1 or a^(2ʳd) ≡ −1 (mod n) for some 0 ≤ r < s; for n < 341,550,071,728,321 the bases 2, 3, 5, 7, 11, 13 and 17 suffice. Its proof that primes pass uses Fermat's little theorem and the square roots ±1 of 1 modulo a prime.
SymPy — Number Theory. The documentation of isprime states that it uses deterministic Miller–Rabin tests for small numbers and that its answer is definitive for n < 2⁶⁴.
Wikipedia — Primality test. Trial division can be limited to 2, 3 and the numbers 6k + 1 and 6k + 5 up to √n, because every prime greater than 3 has one of these two forms.

Problem 128 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

struct Options {
    int target = 2000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--target=", options.target)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.target >= 1;
}

u64 mul_mod(u64 a, u64 b, u64 mod) {
    return static_cast<u64>((static_cast<u128>(a) * static_cast<u128>(b)) % mod);
}

u64 pow_mod(u64 base, u64 exp, u64 mod) {
    u64 result = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if ((exp & 1ULL) != 0ULL) {
            result = mul_mod(result, base, mod);
        }
        base = mul_mod(base, base, mod);
        exp >>= 1ULL;
    }
    return result;
}

bool is_prime(u64 n) {
    if (n < 2) {
        return false;
    }
    for (u64 p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
        if (n == p) {
            return true;
        }
        if (n % p == 0ULL) {
            return false;
        }
    }

    u64 d = n - 1;
    int s = 0;
    while ((d & 1ULL) == 0ULL) {
        d >>= 1ULL;
        ++s;
    }

    for (u64 a : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL}) {
        if (a % n == 0ULL) {
            continue;
        }
        u64 x = pow_mod(a, d, n);
        if (x == 1ULL || x == n - 1) {
            continue;
        }

        bool witness = true;
        for (int r = 1; r < s; ++r) {
            x = mul_mod(x, x, n);
            if (x == n - 1) {
                witness = false;
                break;
            }
        }
        if (witness) {
            return false;
        }
    }

    return true;
}

u64 solve(const int target) {
    if (target == 1) {
        return 1;
    }
    if (target == 2) {
        return 2;
    }

    std::vector<u64> values = {1, 2};

    for (u64 k = 2; static_cast<int>(values.size()) < target; ++k) {
        const u64 a = 6 * k - 1;
        if (is_prime(a) && is_prime(6 * k + 1) && is_prime(12 * k + 5)) {
            values.push_back(3 * k * (k - 1) + 2);
            if (static_cast<int>(values.size()) == target) {
                break;
            }
        }

        if (is_prime(a) && is_prime(6 * k + 5) && is_prime(12 * k - 7)) {
            values.push_back(3 * k * (k + 1) + 1);
            if (static_cast<int>(values.size()) == target) {
                break;
            }
        }
    }

    return values[static_cast<std::size_t>(target - 1)];
}

bool run_checkpoints() {
    if (solve(10) != 271ULL) {
        std::cerr << "Checkpoint failed for target=10" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.target) << '\n';
    return 0;
}

Python

# Problem 128: Hexagonal tile differences
# Find the 2000th tile in the hexagonal grid where PD(n) = 3.
from sympy import isprime

def solve():
    target = 2000
    values = [1, 2]
    k = 2
    while len(values) < target:
        # First cell of ring k: 3k(k-1)+2
        # Last cell of ring k: 3k(k+1)+1
        a = 6*k - 1
        if isprime(a) and isprime(6*k + 1) and isprime(12*k + 5):
            values.append(3*k*(k-1) + 2)
            if len(values) == target: break
        if isprime(a) and isprime(6*k + 5) and isprime(12*k - 7):
            values.append(3*k*(k+1) + 1)
            if len(values) == target: break
        k += 1
    print(values[target - 1])

solve()

Java

public class Euler128 {
    static boolean isPrime(long n) {
        if (n < 2)
            return false;
        if (n < 4)
            return true;
        if (n % 2 == 0 || n % 3 == 0)
            return false;
        for (long p = 5; p * p <= n; p += 6)
            if (n % p == 0 || n % (p + 2) == 0)
                return false;
        return true;
    }

    public static void main(String[] args) {
        int target = 2000;
        long[] values = new long[target];
        values[0] = 1;
        values[1] = 2;
        int cnt = 2;
        for (long k = 2; cnt < target; k++) {
            long a = 6 * k - 1;
            if (isPrime(a) && isPrime(6 * k + 1) && isPrime(12 * k + 5)) {
                values[cnt++] = 3 * k * (k - 1) + 2;
                if (cnt == target)
                    break;
            }
            if (isPrime(a) && isPrime(6 * k + 5) && isPrime(12 * k - 7)) {
                values[cnt++] = 3 * k * (k + 1) + 1;
                if (cnt == target)
                    break;
            }
        }
        System.out.println(values[target - 1]);
    }
}