Project Euler

Linear Combinations of Semiprimes

Given three distinct primes p < q < r, define: f(p,q,r) = 2pqr - pq - qr - rp This is the largest positive integer that cannot be represented as ap + bq + cr for non-negative integers a, b, c (a ge...

Source sync Apr 19, 2026

Problem #0278

Level Level 14

Solved By 1,231

Languages C++, Python

Answer 1228215747273908452

Length 199 words

linear_algebranumber_theoryoptimization

Given the values of integers $1 < a_1 < a_2 < \dots < a_n$, consider the linear combination

$q_1 a_1+q_2 a_2 + \dots + q_n a_n=b$, using only integer values $q_k \ge 0$.

Note that for a given set of $a_k$, it may be that not all values of $b$ are possible.

For instance, if $a_1=5$ and $a_2=7$, there are no $q_1 \ge 0$ and $q_2 \ge 0$ such that $b$ could be

$1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18$ or $23$.

In fact, $23$ is the largest impossible value of $b$ for $a_1=5$ and $a_2=7$.

We therefore call $f(5, 7) = 23$.

Similarly, it can be shown that $f(6, 10, 15)=29$ and $f(14, 22, 77) = 195$.

Find $\displaystyle \sum f( p\, q,p \, r, q \, r)$, where $p$, $q$ and $r$ are prime numbers and $p < q < r < 5000$.

Problem 278: Linear Combinations of Semiprimes

Mathematical Analysis

The Formula

For three pairwise coprime positive integers (which distinct primes always are), the Frobenius-like number is:

f(p,q,r) = 2pqr - pq - qr - rp

Rewriting the Sum

For fixed $p < q$ , summing over all primes $r > q$ up to 5000:

\sum_{r > q} f(p,q,r) = \sum_{r > q} \big[(2pq - p - q) \cdot r - pq\big]

= (2pq - p - q) \cdot \sum_{r > q} r \;-\; pq \cdot |\{r > q\}|

Prefix Sum Optimization

Precompute:

$\text{PS}[i] = \sum_{\text{prime } p \le i} p$ (prefix sum of primes)
$\text{PC}[i] = |\{\text{prime } p \le i\}|$ (prefix count of primes)

Then for fixed $p, q$ :

$\sum r = \text{PS}[5000] - \text{PS}[q]$
$|\{r\}| = \text{PC}[5000] - \text{PC}[q]$

Each $(p, q)$ pair contributes in $O(1)$ .

Editorial

We sieve primes up to 5000. We then build prefix sums and counts. Finally, double loop over prime pairs $p < q$ .

Pseudocode

Sieve primes up to 5000
Build prefix sums and counts
Double loop over prime pairs $p < q$
For each pair, compute the contribution of all valid $r$ in $O(1)$
Accumulate using 128-bit integers

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity

Sieve: $O(N \log \log N)$ with $N = 5000$
Double loop: $O(\pi(5000)^2) = O(669^2) \approx O(450{,}000)$
Total: $O(N \log \log N + \pi(N)^2)$

Answer

\boxed{1228215747273908452}

C++ project_euler/problem_278/solution.cpp

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

/*
 * Problem 278: Linear Combinations of Semiprimes
 *
 * For distinct primes p, q, r, f(p,q,r) = 2pqr - pq - qr - rp.
 * Sum f over all unordered triples {p,q,r} of distinct primes up to 5000.
 *
 * Optimization: for fixed p < q, sum over all primes r > q (up to 5000):
 *   sum_r f(p,q,r) = (2pq - p - q) * (sum of r) - pq * (count of r)
 *
 * Use prefix sums of primes for O(1) per (p,q) pair.
 * Uses __int128 to handle the large answer (~1.2 * 10^18).
 */

int main(){
    const int LIMIT = 5000;

    vector<bool> is_prime(LIMIT + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= LIMIT; i++)
        if (is_prime[i])
            for (int j = i*i; j <= LIMIT; j += i)
                is_prime[j] = false;

    vector<int> primes;
    for (int i = 2; i <= LIMIT; i++)
        if (is_prime[i])
            primes.push_back(i);

    // Prefix sums and counts of primes
    vector<long long> ps(LIMIT + 1, 0);
    vector<int> pc(LIMIT + 1, 0);
    for (int i = 1; i <= LIMIT; i++) {
        ps[i] = ps[i-1] + (is_prime[i] ? i : 0);
        pc[i] = pc[i-1] + (is_prime[i] ? 1 : 0);
    }

    __int128 answer = 0;
    int n = primes.size();

    for (int i = 0; i < n; i++) {
        long long p = primes[i];
        for (int j = i + 1; j < n; j++) {
            long long q = primes[j];

            // r ranges over all primes > q and <= LIMIT
            long long sumR = ps[LIMIT] - ps[q];
            long long countR = pc[LIMIT] - pc[q];
            if (countR == 0) continue;

            __int128 coeff = (__int128)2 * p * q - p - q;
            __int128 contribution = coeff * sumR - (__int128)(p * q) * countR;
            answer += contribution;
        }
    }

    // Print __int128
    string s;
    __int128 x = answer;
    if (x == 0) { cout << 0 << endl; return 0; }
    while (x > 0) { s += '0' + (int)(x % 10); x /= 10; }
    reverse(s.begin(), s.end());
    cout << s << endl;

    return 0;
}

Python project_euler/problem_278/solution.py

#!/usr/bin/env python3
"""
Problem 278: Linear Combinations of Semiprimes

For distinct primes p, q, r, compute f(p,q,r) = 2pqr - pq - qr - rp.
Sum f over all unordered triples {p,q,r} of distinct primes up to 5000.

Uses prefix sums for O(pi(N)^2) efficiency.
"""

def sieve(limit):
    """Return list of primes up to limit."""
    is_prime = [False, False] + [True] * (limit - 1)
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, limit + 1, i):
                is_prime[j] = False
    return [i for i in range(2, limit + 1) if is_prime[i]], is_prime

def solve():
    LIMIT = 5000
    primes, is_prime = sieve(LIMIT)

    # Prefix sums and counts
    ps = [0] * (LIMIT + 1)
    pc = [0] * (LIMIT + 1)
    for i in range(1, LIMIT + 1):
        ps[i] = ps[i-1] + (i if is_prime[i] else 0)
        pc[i] = pc[i-1] + (1 if is_prime[i] else 0)

    answer = 0
    for i, p in enumerate(primes):
        for j in range(i + 1, len(primes)):
            q = primes[j]

            # r ranges over all primes > q, <= LIMIT
            sum_r = ps[LIMIT] - ps[q]
            count_r = pc[LIMIT] - pc[q]
            if count_r == 0:
                continue

            coeff = 2 * p * q - p - q
            answer += coeff * sum_r - p * q * count_r

    return answer

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