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.

Further Reading

1. Problem page: https://projecteuler.net/problem=278
2. Frobenius coin problem: https://en.wikipedia.org/wiki/Coin_problem
3. Numerical semigroups: https://en.wikipedia.org/wiki/Numerical_semigroup