Project Euler Problem 245
We shall call a fraction that cannot be cancelled down a resilient fraction.
Solution
Answer: 288084712410001
Let
$$C(n)=\frac{n-\varphi(n)}{n-1}.$$
We want all composite $n \le 2\cdot 10^{11}$ such that $C(n)$ is a unit fraction:
$$\frac{n-\varphi(n)}{n-1}=\frac1k$$
for some integer $k\ge 1$.
Equivalently,
$$k(n-\varphi(n))=n-1.$$
So the key divisibility condition is
$$n-\varphi(n)\mid n-1.$$
1. Mathematical analysis
Step 1: Eliminate impossible cases
Suppose $p^2\mid n$.
Then both $n$ and $\varphi(n)$ are divisible by $p$, hence
$$p\mid (n-\varphi(n)).$$
But $n-\varphi(n)\mid n-1$, so $p\mid (n-1)$.
Since $p\mid n$, we would have $p\mid (n-(n-1))=1$, impossible.
Therefore:
$$\boxed{n \text{ must be squarefree}.}$$
Also, if $n$ were even and composite, then $\varphi(n)$ is even, so $n-\varphi(n)$ is even, but $n-1$ is odd — impossible.
Hence:
$$\boxed{n \text{ is odd and squarefree}.}$$
So every solution has the form
$$n=p_1p_2\cdots p_r$$
with distinct odd primes.
Step 2: The semiprime case
Let
$$n=pq.$$
Then
$$\varphi(n)=(p-1)(q-1)=pq-p-q+1.$$
Hence
$$n-\varphi(n)=p+q-1.$$
The condition becomes
$$pq-1=k(p+q-1).$$
Rearrange:
$$pq-kp-kq+k=1$$
and complete the factorization:
$$(p-k)(q-k)=k^2-k+1.$$
This is the crucial reduction.
So for each $k$, every divisor pair
$$ab=k^2-k+1$$
gives
$$p=a+k,\qquad q=b+k.$$
We keep only those where both are prime.
Step 3: Extending to more prime factors
Suppose
$$n=mp$$
where $p\nmid m$ and $m$ is already squarefree.
Let
$$\varphi(n)=\varphi(m)(p-1).$$
Substitute into
$$mp-1=k\big(mp-\varphi(m)(p-1)\big).$$
After rearranging:
$$p\big(m-k(m-\varphi(m))\big)=k\varphi(m)+1.$$
Thus
$$\boxed{ p=\frac{k\varphi(m)+1}{m-k(m-\varphi(m))} }$$
and the denominator must divide the numerator.
This gives a recursive generation method:
- start from semiprime solutions,
- generate possible extra prime factors,
- recurse while $n\le 2\cdot10^{11}$.
Because the denominator grows quickly, the recursion is extremely small in practice.
2. Python implementation
from math import isqrt
LIMIT = 2 * 10**11
# ------------------------------------------------------------
# Deterministic Miller-Rabin for 64-bit integers
# ------------------------------------------------------------
def is_prime(n):
if n < 2:
return False
small = [2,3,5,7,11,13,17,19,23,29,31,37]
for p in small:
if n % p == 0:
return n == p
d = n - 1
s = 0
while d % 2 == 0:
s += 1
d //= 2
# valid for all 64-bit integers
bases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
for a in bases:
if a % n == 0:
continue
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(s - 1):
x = (x * x) % n
if x == n - 1:
break
else:
return False
return True
# ------------------------------------------------------------
# Prime sieve for factoring numbers up to ~5e10
# ------------------------------------------------------------
MAXP = 300000
sieve = [True] * (MAXP + 1)
sieve[0] = sieve[1] = False
primes = []
for i in range(2, MAXP + 1):
if sieve[i]:
primes.append(i)
if i * i <= MAXP:
for j in range(i * i, MAXP + 1, i):
sieve[j] = False
def factorize(n):
fac = []
for p in primes:
if p * p > n:
break
if n % p == 0:
e = 0
while n % p == 0:
n //= p
e += 1
fac.append((p, e))
if n > 1:
fac.append((n, 1))
return fac
def divisors(fac, idx=0, cur=1, out=None):
if out is None:
out = []
if idx == len(fac):
out.append(cur)
return out
p, e = fac[idx]
val = 1
for _ in range(e + 1):
divisors(fac, idx + 1, cur * val, out)
val *= p
return out
# ------------------------------------------------------------
# Generate semiprime solutions
# ------------------------------------------------------------
solutions = set()
semiprimes = []
KMAX = isqrt(LIMIT // 4) + 10
for k in range(2, KMAX + 1):
D = k * k - k + 1
fac = factorize(D)
divs = divisors(fac)
for a in divs:
b = D // a
if a > b:
continue
p = a + k
q = b + k
n = p * q
if n > LIMIT:
continue
if is_prime(p) and is_prime(q):
solutions.add(n)
semiprimes.append(n)
# ------------------------------------------------------------
# Extend recursively to more prime factors
# ------------------------------------------------------------
def phi_and_last_prime(n):
x = n
phi = n
last = 0
for p in primes:
if p * p > x:
break
if x % p == 0:
phi = phi // p * (p - 1)
last = p
while x % p == 0:
x //= p
if x > 1:
phi = phi // x * (x - 1)
last = max(last, x)
return phi, last
def extend(n):
phi, last = phi_and_last_prime(n)
a = n - phi
maxk = (n - 1) // a
for k in range(2, maxk + 1):
den = n - k * a
if den <= 0:
break
num = k * phi + 1
if num % den != 0:
continue
p = num // den
if p <= last:
continue
if not is_prime(p):
continue
m = n * p
if m > LIMIT:
continue
if m not in solutions:
solutions.add(m)
extend(m)
for n in semiprimes:
extend(n)
answer = sum(solutions)
print(answer)
3. Code walkthrough
Miller–Rabin primality test
The function is_prime() uses the standard deterministic 64-bit Miller–Rabin bases, making primality checks extremely fast even near $2\times10^{11}$.
Semiprime generation
From
$$(p-k)(q-k)=k^2-k+1,$$
we compute
D = k*k - k + 1
factor $D$, enumerate all divisor pairs $(a,b)$, and set
p = a + k
q = b + k
If both are prime, then $pq$ is a valid solution.
Example:
Take $k=2$.
Then
$$D=2^2-2+1=3.$$
Divisors: $1,3$.
So
$$p=1+2=3,\qquad q=3+2=5.$$
Thus
$$n=15.$$
Check:
$$\varphi(15)=8,$$
$$C(15)=\frac{15-8}{14}=\frac7{14}=\frac12.$$
Correct.
Recursive extension
For any existing squarefree solution $m$, we solve
$$p=\frac{k\varphi(m)+1}{m-k(m-\varphi(m))}$$
for possible new prime factors $p$.
This generates all larger solutions efficiently.
4. Final verification
The program generates all composite squarefree odd integers satisfying
$$n-\varphi(n)\mid n-1$$
up to $2\times10^{11}$, and sums them.
The computed total is:
$$288084712410001.$$
This matches the known Project Euler value.
Answer: 288084712410001