Project Euler

Prime Triplets

Build a triangle of positive integers: Row n contains n numbers. Two numbers are neighbours if they occupy adjacent positions in the triangle, so each entry can have up to 8 neighbours. A prime tri...

Source sync May 21, 2026

Problem #0196

Level Level 09

Solved By 3,054

Languages C++, Python

Answer 322303240771079935

Length 640 words

number_theorygeometrygraph

Build a triangle from all positive integers in the following way:

\[ \begin {array}{ccccccccccc} 1 & & & & & & & & & & \\ \textcolor {red}{2} & \textcolor {red}{3} & & & & & & & & & \\ 4 & \textcolor {red}{5} & 6 & & & & & & & & \\ \textcolor {red}{7} & 8 & 9 & 10 & & & & & & & \\ 11 & 12 & \textcolor {red}{13} & 14 & 15 & & & & & & \\ 16 & \textcolor {red}{17} & 18 & \textcolor {red}{19} & 20 & 21 & & & & & \\ 22 & \textcolor {red}{23} & 24 & 25 & 26 & 27 & 28 & & & & \\ \textcolor {red}{29} & 30 & \textcolor {red}{31} & 32 & 33 & 34 & 35 & 36 & & & \\ \textcolor {red}{37} & 38 & 39 & 40 & \textcolor {red}{41} & 42 & \textcolor {red}{43} & 44 & 45 & & \\ 46 & \textcolor {red}{47} & 48 & 49 & 50 & 51 & 52 & \textcolor {red}{53} & 54 & 55 & \\ 56 & 57 & 58 & \textcolor {red}{59} & 60 & \textcolor {red}{61} & 62 & 63 & 64 & 65 & 66 \\ & & & & & \ldots & & & & & \end {array} \]

Each positive integer has up to eight neighbours in the triangle.

A set of three primes is called a prime triplet if one of the three primes has the other two as neighbours in the triangle.

For example, in the second row, the prime numbers $2$ and $3$ are elements of some prime triplet.

If row $8$ is considered, it contains two primes which are elements of some prime triplet, i.e. $29$ and $31$.

If row $9$ is considered, it contains only one prime which is an element of some prime triplet: $37$.

Define $S(n)$ as the sum of the primes in row $n$ which are elements of any prime triplet.

Then $S(8)=60$ and $S(9)=37$.

You are given that $S(10000)=950007619$.

Find $S(5678027) + S(7208785)$.

Problem 196: Prime Triplets

Mathematical Development

Theorem 1. (Triangle Indexing.) Row $n$ (1-indexed) contains the integers from $T(n) = \frac{n(n-1)}{2} + 1$ to $\frac{n(n+1)}{2}$ . Position $k$ (0-indexed) in row $n$ has value $T(n) + k$ .

Proof. Row 1 has 1 element, row 2 has 2, …, row $n-1$ has $n-1$ . The total count before row $n$ is $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}$ . Thus row $n$ starts at $\frac{n(n-1)}{2} + 1$ . $\square$

Theorem 2. (Neighbour Structure.) Position $(n, k)$ has at most 6 neighbours:

Same row: $(n, k-1)$ and $(n, k+1)$ (when they exist).
Row above ( $n-1$ ): positions $(n-1, k-1)$ and $(n-1, k)$ (when valid, i.e., $0 \leq k-1$ and $k \leq n-2$ ).
Row below ( $n+1$ ): positions $(n+1, k)$ and $(n+1, k+1)$ .

Proof. In the triangular arrangement, each position touches at most 2 positions in its own row (left and right), 2 in the row above (up-left and up-right), and 2 in the row below (down-left and down-right). The index mapping follows from the triangular geometry. $\square$

Lemma 1. (Parity Constraint.) For $n \geq 4$ , two positions in the same row that are adjacent hold consecutive integers, so at most one can be prime (since one is even). Therefore, prime triplets in large rows must have the “center” prime’s two prime neighbours in adjacent rows, not in the same row.

Proof. Adjacent positions in row $n$ hold values $T(n) + k$ and $T(n) + k + 1$ , which are consecutive integers. For values $> 2$ , at most one of two consecutive integers is prime. $\square$

Theorem 3. (Membership Criterion.) A prime $p$ at position $(n, k)$ belongs to a prime triplet if and only if at least one of the following holds:

(Center condition:) $p$ has at least 2 prime neighbours.
(Spoke condition:) $p$ has a prime neighbour $q$ that itself has at least 2 prime neighbours (so $q$ is the center, and $p$ is one of the spokes).

Proof. A prime triplet is a set $\{p, q, r\}$ where one element (say $q$ ) is a neighbour of both $p$ and $r$ . If $p$ is in such a triplet, either $p$ is the center (condition 1, with $q$ and $r$ as its prime neighbours) or $p$ is a spoke (condition 2, where $q$ is the center and has another prime neighbour $r$ ). These exhaust all possibilities. $\square$

Lemma 2. (Search Radius.) To evaluate conditions 1 and 2 for primes in row $n$ , we need primality information for rows $n-2$ through $n+2$ . Condition 2 requires checking neighbours of neighbours, which can reach 2 rows away.

Proof. A neighbour of a position in row $n$ is in row $n-1$ , $n$ , or $n+1$ . A neighbour of that neighbour can be in rows $n-2$ through $n+2$ . $\square$

Editorial

The target row is enormous, so the only viable approach is to work locally. A prime in row n can only be affected by numbers in neighboring rows, and the spoke condition only reaches one layer farther, so a segmented sieve over rows n-3 through n+3 is enough. That reduces the primality work to a short interval of length O(n) instead of sieving all the way up to the values in row n.

Once primality in that band is known, membership in a prime triplet is a local graph test. A prime in the target row is valid if it is itself a center with at least two prime neighbours, or if one of its prime neighbours is such a center. The implementation therefore counts prime neighbours on demand inside the sieved band and then performs one pass across the target row, adding exactly the primes that satisfy one of those two conditions.

Pseudocode

Define solve_row(n):
    determine the numeric interval covering rows n-3 through n+3;
    segmented-sieve that interval.

    For any prime position in the band, be able to count its prime neighbours
    in the same row, the row above, and the row below.

    Scan every value in row n:
        skip composites;
        add the prime immediately if it has at least two prime neighbours;
        otherwise, inspect its prime neighbours and add it if one of them
        has at least two prime neighbours.

Return solve_row(5678027) + solve_row(7208785).

Complexity Analysis

Time: The values in row $n$ are $\Theta(n^2)$ . The segmented sieve covers $O(n)$ values in 5 rows, requiring small primes up to $O(n)$ . Sieving small primes: $O(n \log \log n)$ . Segmented sieve: $O(n \log \log n)$ . Neighbour checks: $O(n)$ with constant factor (at most 6 neighbours, each with at most 6 neighbours). Total: $O(n \log \log n)$ .
Space: $O(n)$ for the sieve bitmap over 5 rows, plus $O(n / \ln n)$ for small primes.

Answer

\boxed{322303240771079935}

C++ project_euler/problem_196/solution.cpp

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

// Problem 196: Prime Triplets
//
// Triangle: row n has values T(n)+0, T(n)+1, ..., T(n)+n-1 where T(n) = n*(n-1)/2 + 1.
//
// Neighbors of (n, k) [0-indexed]:
//   Same row: (n, k-1), (n, k+1)
//   Row above (n-1): (n-1, k-1), (n-1, k), (n-1, k+1) [if valid]
//   Row below (n+1): (n+1, k-1), (n+1, k), (n+1, k+1) [if valid]
//   Up to 8 neighbors total.
//
// Prime triplet: 3 primes where ONE has the other TWO as neighbors.
// NOT a clique -- a star/path with the center having 2+ prime neighbors.
//
// A prime p in row n is in a triplet iff:
//   (a) p has >= 2 prime neighbors, OR
//   (b) p has a prime neighbor q that has >= 2 prime neighbors (q is center, p is spoke)
//
// Algorithm:
// 1. Sieve primes in rows n-3 to n+3 (need 3-row buffer to check neighbors of neighbors)
// 2. Count prime neighbors for each prime in rows n-2 to n+2
// 3. Mark primes in row n that satisfy (a) or (b)

ll row_start(ll n) {
    return n * (n - 1) / 2 + 1;
}

vector<char> segmented_sieve(ll lo, ll hi) {
    ll range = hi - lo + 1;
    vector<char> is_prime(range, 1);
    if (lo <= 0) {
        for (ll i = 0; i < min(range, 1 - lo + 1); i++)
            is_prime[i] = 0;
    }
    if (lo <= 1 && 1 <= hi) is_prime[1 - lo] = 0;

    ll sqrt_hi = (ll)sqrt((double)hi) + 2;
    vector<char> small(sqrt_hi + 1, 1);
    small[0] = small[1] = 0;
    for (ll i = 2; i <= sqrt_hi; i++) {
        if (small[i]) {
            for (ll j = i * i; j <= sqrt_hi; j += i)
                small[j] = 0;
            ll start = max(i * i, ((lo + i - 1) / i) * i);
            for (ll j = start; j <= hi; j += i)
                is_prime[j - lo] = 0;
        }
    }
    return is_prime;
}

ll solve(ll n) {
    // Need rows n-3 to n+3 for the full neighbor-of-neighbor check
    ll r_min = max(1LL, n - 3);
    ll r_max = n + 3;
    ll lo = row_start(r_min);
    ll hi = row_start(r_max) + r_max - 1;

    auto sieve = segmented_sieve(lo, hi);

    auto prime = [&](ll v) -> bool {
        if (v < lo || v > hi) return false;
        return sieve[v - lo];
    };

    // For each prime in rows n-2..n+2, count how many prime neighbors it has.
    // A prime with >= 2 prime neighbors is a "center" of at least one triplet.
    // Store: for each cell in rows n-2..n+2, the count of prime neighbors.

    // We'll work row by row. For efficiency, store prime neighbor counts.
    // But we only need to know: for each prime in rows n-1, n, n+1,
    // does it have >= 2 prime neighbors?
    // And for primes in row n: also check if any neighbor has >= 2 prime neighbors.

    // Step 1: For each prime in rows n-2..n+2, count prime neighbors
    // (neighbors span rows r-1..r+1, so we need rows n-3..n+3 in the sieve)

    // For memory efficiency: store "has_2_prime_nbs" flag for primes in rows n-2..n+2
    // Then for row n: check condition (a) or (b).

    // Actually let's just compute for rows n-1, n, n+1 whether each prime has >= 2 prime nbs.
    // For condition (b), a prime p in row n needs a neighbor q in rows n-1 or n+1 (or n)
    // that has >= 2 prime neighbors. q's neighbors span rows n-2..n+2.

    // So we need "has_2_prime_nbs" for primes in rows n-1, n, n+1.
    // To compute that, we need prime status in rows n-2..n+2.
    // The sieve covers rows n-3..n+3, which is sufficient.

    // Build arrays of "has >= 2 prime neighbors" for rows n-1, n, n+1
    auto count_prime_nbs = [&](ll row, ll pos) -> int {
        int cnt = 0;
        ll rs = row_start(row);
        ll v = rs + pos;
        // Same row
        if (pos > 0 && prime(v - 1)) cnt++;
        if (pos < row - 1 && prime(v + 1)) cnt++;
        // Row above
        if (row > 1) {
            ll above = row_start(row - 1);
            for (int dk = -1; dk <= 1; dk++) {
                ll p = pos + dk;
                if (p >= 0 && p < row - 1) {
                    if (prime(above + p)) cnt++;
                }
            }
        }
        // Row below
        {
            ll below = row_start(row + 1);
            for (int dk = -1; dk <= 1; dk++) {
                ll p = pos + dk;
                if (p >= 0 && p < row + 1) {
                    if (prime(below + p)) cnt++;
                }
            }
        }
        return cnt;
    };

    // For each prime in row n, check:
    // (a) it has >= 2 prime neighbors
    // (b) it has a prime neighbor (in rows n-1, n, n+1) that has >= 2 prime neighbors

    ll n_start = row_start(n);
    ll result = 0;

    for (ll k = 0; k < n; k++) {
        ll v = n_start + k;
        if (!prime(v)) continue;

        int my_cnt = count_prime_nbs(n, k);
        if (my_cnt >= 2) {
            result += v;
            continue;
        }

        // Check condition (b): does any prime neighbor have >= 2 prime neighbors?
        bool found = false;

        // Same row neighbors
        if (k > 0 && prime(v - 1)) {
            if (count_prime_nbs(n, k - 1) >= 2) { found = true; }
        }
        if (!found && k < n - 1 && prime(v + 1)) {
            if (count_prime_nbs(n, k + 1) >= 2) { found = true; }
        }

        // Row above neighbors
        if (!found && n > 1) {
            ll above = row_start(n - 1);
            for (int dk = -1; dk <= 1 && !found; dk++) {
                ll p = k + dk;
                if (p >= 0 && p < n - 1 && prime(above + p)) {
                    if (count_prime_nbs(n - 1, p) >= 2) { found = true; }
                }
            }
        }

        // Row below neighbors
        if (!found) {
            ll below = row_start(n + 1);
            for (int dk = -1; dk <= 1 && !found; dk++) {
                ll p = k + dk;
                if (p >= 0 && p < n + 1 && prime(below + p)) {
                    if (count_prime_nbs(n + 1, p) >= 2) { found = true; }
                }
            }
        }

        if (found) result += v;
    }

    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    ll ans = solve(5678027) + solve(7208785);
    cout << ans << endl;
    return 0;
}

Python project_euler/problem_196/solution.py

"""
Project Euler Problem 196: Prime Triplets

Compute S(5678027) + S(7208785) with a segmented sieve on the relevant rows.
"""

import math
from functools import lru_cache


def row_start(n):
    return n * (n - 1) // 2 + 1


def segmented_sieve(lo, hi):
    size = hi - lo + 1
    is_prime = bytearray(b"\x01") * size
    if lo <= 0:
        for i in range(min(size, 1 - lo + 1)):
            is_prime[i] = 0
    if lo <= 1 <= hi:
        is_prime[1 - lo] = 0

    sqrt_hi = int(math.isqrt(hi)) + 2
    small = bytearray(b"\x01") * (sqrt_hi + 1)
    small[0] = small[1] = 0
    for i in range(2, sqrt_hi + 1):
        if small[i]:
            for j in range(i * i, sqrt_hi + 1, i):
                small[j] = 0
            start = max(i * i, ((lo + i - 1) // i) * i)
            for j in range(start, hi + 1, i):
                is_prime[j - lo] = 0
    return is_prime


def solve(n):
    r_min = max(1, n - 3)
    r_max = n + 3
    lo = row_start(r_min)
    hi = row_start(r_max) + r_max - 1
    sieve = segmented_sieve(lo, hi)

    def is_prime(value):
        if value < lo or value > hi:
            return False
        return sieve[value - lo] == 1

    @lru_cache(maxsize=None)
    def count_prime_neighbors(row, pos):
        count = 0
        start = row_start(row)
        value = start + pos

        if pos > 0 and is_prime(value - 1):
            count += 1
        if pos < row - 1 and is_prime(value + 1):
            count += 1

        if row > 1:
            above = row_start(row - 1)
            for delta in (-1, 0, 1):
                neighbor = pos + delta
                if 0 <= neighbor < row - 1 and is_prime(above + neighbor):
                    count += 1

        below = row_start(row + 1)
        for delta in (-1, 0, 1):
            neighbor = pos + delta
            if 0 <= neighbor < row + 1 and is_prime(below + neighbor):
                count += 1

        return count

    target_start = row_start(n)
    total = 0

    for pos in range(n):
        value = target_start + pos
        if not is_prime(value):
            continue

        if count_prime_neighbors(n, pos) >= 2:
            total += value
            continue

        found = False

        if pos > 0 and is_prime(value - 1) and count_prime_neighbors(n, pos - 1) >= 2:
            found = True
        if not found and pos < n - 1 and is_prime(value + 1) and count_prime_neighbors(n, pos + 1) >= 2:
            found = True

        if not found and n > 1:
            above = row_start(n - 1)
            for delta in (-1, 0, 1):
                neighbor = pos + delta
                if 0 <= neighbor < n - 1 and is_prime(above + neighbor):
                    if count_prime_neighbors(n - 1, neighbor) >= 2:
                        found = True
                        break

        if not found:
            below = row_start(n + 1)
            for delta in (-1, 0, 1):
                neighbor = pos + delta
                if 0 <= neighbor < n + 1 and is_prime(below + neighbor):
                    if count_prime_neighbors(n + 1, neighbor) >= 2:
                        found = True
                        break

        if found:
            total += value

    return total


def main():
    assert solve(8) == 60
    assert solve(9) == 37
    assert solve(10000) == 950007619
    print(solve(5678027) + solve(7208785))


if __name__ == "__main__":
    main()