Problem 278: Linear Combinations of Semiprimes

Project Euler Problem 278 Solution

EulerSolve provides an optimized solution for Project Euler Problem 278, Linear Combinations of Semiprimes, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For distinct primes $p \lt q \lt r$, define the three semiprimes $$a=pq,\qquad b=pr,\qquad c=qr.$$ For each prime triple, we want the largest integer that cannot be written as a nonnegative linear combination of $a,b,c$. Then we sum that Frobenius value over all triples below the prime limit. As usual, the final Project Euler number is omitted; the purpose of this page is to explain the mathematics behind the C++ solution. Mathematical Approach 1) The semigroup we need to understand Let $$S=\langle pq,pr,qr\rangle=\{x\cdot pq+y\cdot pr+z\cdot qr:\ x,y,z\ge0\}.$$ The problem asks for the Frobenius number of this semigroup, namely the largest integer not belonging to $S$. For three arbitrary generators, no simple closed formula usually exists. The reason this problem is solvable is that the generators share the prime factors $p,q,r$ in a very rigid way. 2) Rewrite every representable number by residue modulo $p$ Because $$pq=p\cdot q,\qquad pr=p\cdot r,$$ every representable number has the form $$N=z\cdot qr+p\cdot m,$$ where $$m\in \langle q,r\rangle=\{u\cdot q+v\cdot r:\ u,v\ge0\}.$$ So the whole three-generator problem reduces to this question: For each residue class modulo $p$, how large can $N$ be before the quotient part $m$ is forced into the two-generator semigroup $\langle q,r\rangle$?...

Detailed mathematical approach

Problem Summary

For distinct primes $p \lt q \lt r$, define the three semiprimes

$$a=pq,\qquad b=pr,\qquad c=qr.$$

For each prime triple, we want the largest integer that cannot be written as a nonnegative linear combination of $a,b,c$. Then we sum that Frobenius value over all triples below the prime limit. As usual, the final Project Euler number is omitted; the purpose of this page is to explain the mathematics behind the C++ solution.

Mathematical Approach

1) The semigroup we need to understand

Let

$$S=\langle pq,pr,qr\rangle=\{x\cdot pq+y\cdot pr+z\cdot qr:\ x,y,z\ge0\}.$$

The problem asks for the Frobenius number of this semigroup, namely the largest integer not belonging to $S$.

For three arbitrary generators, no simple closed formula usually exists. The reason this problem is solvable is that the generators share the prime factors $p,q,r$ in a very rigid way.

2) Rewrite every representable number by residue modulo $p$

Because

$$pq=p\cdot q,\qquad pr=p\cdot r,$$

every representable number has the form

$$N=z\cdot qr+p\cdot m,$$

where

$$m\in \langle q,r\rangle=\{u\cdot q+v\cdot r:\ u,v\ge0\}.$$

So the whole three-generator problem reduces to this question:

For each residue class modulo $p$, how large can $N$ be before the quotient part $m$ is forced into the two-generator semigroup $\langle q,r\rangle$?

Since $p$ is distinct from $q$ and $r$,

$$\gcd(qr,p)=1.$$

Therefore multiplication by $qr$ permutes the residue classes modulo $p$. So for every integer $N$, there is a unique choice

$$x\in\{0,1,\dots,p-1\}$$

such that

$$N\equiv x\cdot qr \pmod p.$$

For that unique $x$, we can write

$$N=x\cdot qr+p\cdot m$$

with integer $m$.

3) The two-generator core: Sylvester for $q$ and $r$

Now $q$ and $r$ are coprime primes, so the classical two-generator Frobenius theorem applies:

$$g(q,r)=qr-q-r.$$

This means:

$$m\notin\langle q,r\rangle\quad\Longrightarrow\quad m\le qr-q-r,$$

and every integer

$$m\gt qr-q-r$$

does belong to $\langle q,r\rangle$.

4) Largest nonrepresentable number in one fixed residue class

Fix a residue representative $x\in\{0,\dots,p-1\}$. Consider numbers of the form

$$N=x\cdot qr+p\cdot m.$$

If $m\gt qr-q-r$, then $m\in\langle q,r\rangle$, hence $N\in S$. Therefore the only candidates for nonrepresentability in this residue class occur when

$$m\le qr-q-r.$$

This suggests that the largest missing number in the residue class should be

$$G_x=x\cdot qr+p(qr-q-r).$$

Why is $G_x$ not representable? Suppose, for contradiction, that $G_x\in S$. Then

$$G_x=z\cdot qr+p(q u+r v)$$

for some $z,u,v\ge0$. Because $qr$ is invertible modulo $p$, the residue condition forces

$$z\equiv x\pmod p,$$

so we can write

$$z=x+p t,\qquad t\ge0.$$

Substitute this into the equation for $G_x$:

$$x\cdot qr+p(qr-q-r)=(x+p t)\cdot qr+p(q u+r v).$$

After subtracting $x\cdot qr$ and dividing by $p$, we get

$$qr-q-r=t\cdot qr+q u+r v.$$

If $t\ge1$, then the right-hand side is at least $qr$, impossible because the left-hand side is $qr-q-r\lt qr$. So $t=0$, and then

$$qr-q-r=q u+r v,$$

contradicting the fact that $qr-q-r$ is the Frobenius number for $q$ and $r$. Hence $G_x\notin S$.

Why is every larger number in the same residue class representable? Let

$$N\gt G_x$$

and suppose $N\equiv x\cdot qr\pmod p$. Then

$$N=x\cdot qr+p m$$

for some integer $m$, and because $N\gt G_x$, we have

$$m\gt qr-q-r.$$

So $m\in\langle q,r\rangle$, which implies $N\in S$.

Therefore $G_x$ is exactly the largest nonrepresentable integer in its residue class.

5) Maximize over all residue classes

Now the global Frobenius number is simply the maximum of the $G_x$:

$$g(pq,pr,qr)=\max_{0\le x\le p-1}\Bigl(x\cdot qr+p(qr-q-r)\Bigr).$$

This is largest at $x=p-1$, so

$$g(pq,pr,qr)=(p-1)qr+p(qr-q-r).$$

Expand it:

$$g(pq,pr,qr)=2pqr-pq-pr-qr.$$

This is the exact closed formula used by the code.

6) Worked example: $(p,q,r)=(2,3,5)$

The generators are

$$6,\ 10,\ 15.$$

For the two-generator core,

$$g(3,5)=15-3-5=7.$$

Because $p=2$, there are only two residue classes modulo $2$:

For $x=0$, the largest missing number is

$$G_0=0\cdot15+2\cdot7=14.$$

For $x=1$, the largest missing number is

$$G_1=1\cdot15+2\cdot7=29.$$

So the global answer is $29$. This matches the explicit nonrepresentability check:

$$29\notin\langle6,10,15\rangle,$$

while the next few numbers are already representable:

$$30=15+15,\quad 31=15+10+6,\quad 32=10+10+6+6,\quad 33=15+6+6+6.$$

7) Second checkpoint example: $(2,7,11)$

Here

$$g(7,11)=77-7-11=59.$$

Again $p=2$, so

$$G_0=2\cdot59=118,\qquad G_1=77+2\cdot59=195.$$

Hence

$$g(14,22,77)=195,$$

which is exactly the second checkpoint hard-coded in the program.

8) Summation over all prime triples

Once the Frobenius number has a closed form, the original problem becomes

$$\sum_{p \lt q \lt r \lt L}\bigl(2pqr-pq-pr-qr\bigr).$$

So the hard mathematics is entirely in the formula above; after that, the remaining task is just prime generation and triple enumeration.

How the Code Works

1) Prime sieve. primes_below(limit) generates all primes below the chosen limit.

2) Closed formula helper. frobenius_semiprime_triple(p,q,r) returns

$$2pqr-pq-pr-qr.$$

3) Brute-force validation on small cases. brute_frobenius_three(a,b,c) builds a reachability table and checks that the formula agrees with brute force for all prime triples below $20$.

4) Final accumulation. solve_sum() iterates over all ordered triples $p \lt q \lt r$ and accumulates the result in a 128-bit integer.

5) Small total checkpoint. For primes below $10$, the four triples are $(2,3,5)$, $(2,3,7)$, $(2,5,7)$, $(3,5,7)$, giving

$$29+43+81+139=292.$$

Complexity Analysis

If $m=\pi(L)$ is the number of primes below $L$, the sieve costs about $O(L\log\log L)$, while the triple enumeration costs $O(m^3)$. That cubic triple loop dominates the runtime. Memory usage is $O(m)$ for the prime list, plus a small extra table used only by the brute-force checkpoints.

Problem 278 source code

C++

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

namespace {

using u64 = std::uint64_t;
using u128 = __uint128_t;

struct Options {
    int prime_limit = 5000;
    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, "--prime-limit=", options.prime_limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.prime_limit >= 3;
}

std::vector<int> primes_below(const int limit) {
    std::vector<bool> is_prime(static_cast<std::size_t>(limit), true);
    if (limit > 0) {
        is_prime[0] = false;
    }
    if (limit > 1) {
        is_prime[1] = false;
    }

    for (int p = 2; p * p < limit; ++p) {
        if (!is_prime[static_cast<std::size_t>(p)]) {
            continue;
        }
        for (int x = p * p; x < limit; x += p) {
            is_prime[static_cast<std::size_t>(x)] = false;
        }
    }

    std::vector<int> primes;
    for (int p = 2; p < limit; ++p) {
        if (is_prime[static_cast<std::size_t>(p)]) {
            primes.push_back(p);
        }
    }
    return primes;
}

u64 frobenius_semiprime_triple(const u64 p, const u64 q, const u64 r) {
    return 2ULL * p * q * r - p * q - p * r - q * r;
}

std::string to_string_u128(u128 x) {
    if (x == 0) {
        return "0";
    }
    std::string s;
    while (x > 0) {
        const int digit = static_cast<int>(x % 10);
        s.push_back(static_cast<char>('0' + digit));
        x /= 10;
    }
    std::reverse(s.begin(), s.end());
    return s;
}

u128 solve_sum(const int prime_limit) {
    const std::vector<int> primes = primes_below(prime_limit);

    u128 answer = 0;
    const int n = static_cast<int>(primes.size());
    for (int i = 0; i < n; ++i) {
        const u64 p = static_cast<u64>(primes[static_cast<std::size_t>(i)]);
        for (int j = i + 1; j < n; ++j) {
            const u64 q = static_cast<u64>(primes[static_cast<std::size_t>(j)]);
            for (int k = j + 1; k < n; ++k) {
                const u64 r = static_cast<u64>(primes[static_cast<std::size_t>(k)]);
                answer += static_cast<u128>(frobenius_semiprime_triple(p, q, r));
            }
        }
    }
    return answer;
}

u64 brute_frobenius_three(const u64 a, const u64 b, const u64 c) {
    const u64 cap = 4 * a * b * c;
    std::vector<bool> can(static_cast<std::size_t>(cap + 1), false);
    can[0] = true;

    for (u64 x = 0; x <= cap; ++x) {
        if (!can[static_cast<std::size_t>(x)]) {
            continue;
        }
        if (x + a <= cap) {
            can[static_cast<std::size_t>(x + a)] = true;
        }
        if (x + b <= cap) {
            can[static_cast<std::size_t>(x + b)] = true;
        }
        if (x + c <= cap) {
            can[static_cast<std::size_t>(x + c)] = true;
        }
    }

    u64 best = 0;
    for (u64 x = 1; x <= cap; ++x) {
        if (!can[static_cast<std::size_t>(x)]) {
            best = x;
        }
    }
    return best;
}

bool run_checkpoints() {
    if (frobenius_semiprime_triple(2, 3, 5) != 29ULL) {
        std::cerr << "Checkpoint failed for (2,3,5)" << '\n';
        return false;
    }
    if (frobenius_semiprime_triple(2, 7, 11) != 195ULL) {
        std::cerr << "Checkpoint failed for (2,7,11)" << '\n';
        return false;
    }

    // Verify formula against brute force on a small prime pool.
    const std::vector<int> small_primes = primes_below(20);
    for (std::size_t i = 0; i < small_primes.size(); ++i) {
        for (std::size_t j = i + 1; j < small_primes.size(); ++j) {
            for (std::size_t k = j + 1; k < small_primes.size(); ++k) {
                const u64 p = static_cast<u64>(small_primes[i]);
                const u64 q = static_cast<u64>(small_primes[j]);
                const u64 r = static_cast<u64>(small_primes[k]);
                const u64 a = p * q;
                const u64 b = p * r;
                const u64 c = q * r;
                const u64 brute = brute_frobenius_three(a, b, c);
                const u64 formula = frobenius_semiprime_triple(p, q, r);
                if (brute != formula) {
                    std::cerr << "Formula mismatch for (" << p << ',' << q << ',' << r
                              << "): brute=" << brute << ", formula=" << formula << '\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 << to_string_u128(solve_sum(options.prime_limit)) << '\n';
    return 0;
}

Python

def solve():
    prime_limit = 5000

    def primes_below(limit):
        is_p = bytearray(b'\x01' * limit)
        is_p[0] = 0
        is_p[1] = 0
        for p in range(2, limit):
            if p * p >= limit:
                break
            if is_p[p]:
                for q in range(p*p, limit, p):
                    is_p[q] = 0
        return [p for p in range(2, limit) if is_p[p]]

    primes = primes_below(prime_limit)
    n = len(primes)
    answer = 0
    for i in range(n):
        p = primes[i]
        for j in range(i + 1, n):
            q = primes[j]
            pq = p * q
            for k in range(j + 1, n):
                r = primes[k]
                answer += 2 * pq * r - pq - p * r - q * r
    return str(answer)

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

Java

import java.util.*;

public class Euler278 {
    static List<Integer> primesBelow(int limit) {
        boolean[] isPrime = new boolean[limit];
        Arrays.fill(isPrime, true);
        if (limit > 0)
            isPrime[0] = false;
        if (limit > 1)
            isPrime[1] = false;

        for (int p = 2; p * p < limit; ++p) {
            if (!isPrime[p])
                continue;
            for (int x = p * p; x < limit; x += p) {
                isPrime[x] = false;
            }
        }

        List<Integer> primes = new ArrayList<>();
        for (int p = 2; p < limit; ++p) {
            if (isPrime[p]) {
                primes.add(p);
            }
        }
        return primes;
    }

    static long frobeniusSemiprimeTriple(long p, long q, long r) {
        return 2L * p * q * r - p * q - p * r - q * r;
    }

    public static String solve() {
        int primeLimit = 5000;
        List<Integer> primes = primesBelow(primeLimit);
        int n = primes.size();

        // 128-bit emulation for summing large numbers is necessary if the sum exceeds
        // Long.MAX_VALUE.
        // However, max prime is 5000.
        // There are ~669 primes. Number of combinations is (669 choose 3) ~ 50,000,000
        // Average value of frobenius is 2 * p * q * r where p,q,r <= 5000.
        // Max value is 2 * 5000^3 = 2.5e11
        // Expected sum: 2.5e11 * 5e7 = 1.25e19, which fits in an unsigned 64-bit int,
        // but Long.MAX_VALUE is 9e18. So it will overflow a signed long!
        // Wait, the output from C++ is 1228215747273908452.
        // Does 1228215747273908452 fit in a signed long?
        // 1.22e18 fits safely in a signed 64-bit int (Long.MAX_VALUE is 9.22e18).

        long answer = 0;
        for (int i = 0; i < n; ++i) {
            long p = primes.get(i);
            for (int j = i + 1; j < n; ++j) {
                long q = primes.get(j);
                for (int k = j + 1; k < n; ++k) {
                    long r = primes.get(k);
                    answer += frobeniusSemiprimeTriple(p, q, r);
                }
            }
        }
        return String.valueOf(answer);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}