Project Euler Problem 531

Solution

Answer: 4515432351156203105

We need to compute

$$\sum_{1000000 \le n < m < 1005000} f(n,m)$$

where

$$f(n,m)=g(\phi(n),n,\phi(m),m),$$

and $g(a,n,b,m)$ is the smallest non-negative solution to

$$x\equiv a \pmod n,\qquad x\equiv b \pmod m,$$

or $0$ if no solution exists.

The natural approach is:

Precompute Euler’s totient function $\phi(n)$ for all $n\in[10^6,1004999]$ using a sieve.
For every pair $(n,m)$, solve the CRT system:

$$x\equiv \phi(n)\pmod n,\qquad x\equiv \phi(m)\pmod m.$$ 3. If the congruences are incompatible modulo $\gcd(n,m)$, contribute $0$. 4. Otherwise compute the minimal solution using the generalized Chinese Remainder Theorem.

The exact Python code used:

from math import gcd

L = 1000000
R = 1005000

# Compute Euler phi values by sieve
phi = list(range(R + 1))

for i in range(2, R + 1):
    if phi[i] == i:  # prime
        for j in range(i, R + 1, i):
            phi[j] -= phi[j] // i

def crt(a, n, b, m):
    g = gcd(n, m)

    # No solution
    if (b - a) % g:
        return 0

    ng = n // g
    mg = m // g
    rhs = (b - a) // g

    # Solve ng * t ≡ rhs (mod mg)
    inv = pow(ng, -1, mg)
    t = (rhs * inv) % mg

    lcm = ng * m
    x = (a + n * t) % lcm
    return x

# Verify examples
print(crt(2,4,4,6))  # 10
print(crt(3,4,4,6))  # 0

total = 0

for n in range(L, R):
    an = phi[n]
    for m in range(n + 1, R):
        total += crt(an, n, phi[m], m)

print(total)

The verification examples match the statement:

$g(2,4,4,6)=10$
$g(3,4,4,6)=0$

Running the full computation gives:

$$4515432351156203105$$

Answer: 4515432351156203105