Project Euler Problem 278

Solution

Answer: 1228215747273908452

Let

$$a_1=pq,\qquad a_2=pr,\qquad a_3=qr$$

for distinct primes $p<q<r$.

We need

$$\sum_{p<q<r<5000} f(pq,pr,qr).$$

The key is to derive a closed formula for $f(pq,pr,qr)$.

1. Mathematical analysis

We are looking for the largest impossible nonnegative integer combination

$$x(pq)+y(pr)+z(qr)=b, \qquad x,y,z\ge 0.$$

This is a Frobenius-type problem.

Step 1: Observe pairwise gcd structure

For

$$a=pq,\quad b=pr,\quad c=qr,$$

we have

$$\gcd(a,b)=p,\qquad \gcd(a,c)=q,\qquad \gcd(b,c)=r,$$

and

$$\gcd(a,b,c)=1.$$

These triples form a special numerical semigroup.

A classical result for triples of the form

$$(ab,ac,bc)$$

with pairwise coprime $a,b,c$ gives the Frobenius number:

$$f(ab,ac,bc)=2abc-ab-ac-bc.$$

Here the pairwise coprime parameters are exactly $p,q,r$, so:

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

Step 2: Verify against the examples

Example 1

$$(6,10,15)=(2\cdot3,\ 2\cdot5,\ 3\cdot5)$$

Formula gives:

$$2(2)(3)(5)-6-10-15 = 60-31 = 29.$$

Matches the problem statement.

Example 2

$$(14,22,77)=(2\cdot7,\ 2\cdot11,\ 7\cdot11)$$

$$2(2)(7)(11)-14-22-77 = 308-113 = 195.$$

Again matches.

So the sum becomes

$$S = \sum_{p<q<r<5000} \left(2pqr-pq-pr-qr\right).$$

2. Python implementation

from sympy import primerange

# Generate all primes < 5000
primes = list(primerange(2, 5000))

# Prefix sums of primes for fast summation
prefix_sum = [0]
for p in primes:
    prefix_sum.append(prefix_sum[-1] + p)

total = 0

# O(n^2) summation over q,r
for k in range(2, len(primes)):
    r = primes[k]

    for j in range(1, k):
        q = primes[j]

        # Sum of p for p < q
        sum_p = prefix_sum[j]
        count_p = j

        # Sum over all p < q:
        # Σ (2pqr - pq - pr - qr)
        total += (
            (2 * q * r - q - r) * sum_p
            - q * r * count_p
        )

print(total)

3. Code walkthrough

Prime generation

primes = list(primerange(2, 5000))

Creates all primes less than $5000$.

There are $669$ such primes.

Prefix sums

prefix_sum.append(prefix_sum[-1] + p)

Stores

$$P(j)=\sum_{i<j} p_i$$

so we can quickly evaluate sums over all $p<q$.

Main summation

For fixed $q,r$,

$$\sum_{p<q} (2pqr-pq-pr-qr)$$

becomes

$$(2qr-q-r)\sum_{p<q}p - qr\cdot #{p<q}.$$

This reduces the complexity from $O(n^3)$ to $O(n^2)$.

Example check

For $(2,3,5)$:

2*2*3*5 - 6 - 10 - 15

gives:

$$60-31=29$$

matching $f(6,10,15)=29$.

4. Final verification

Formula matches both examples exactly.
Number of prime triples is

$$\binom{669}{3}\approx 5\times 10^7,$$

so an $O(n^3)$ brute force would be wasteful; the $O(n^2)$ method is appropriate.

Result is positive and of plausible magnitude (about $10^{18}$) given cubic prime products.

Answer: 1228215747273908452