Detailed mathematical approach

Problem Summary

For a fixed denominator \(d\), the proper fractions are

$\frac{1}{d},\frac{2}{d},\dots,\frac{d-1}{d}.$

A proper fraction is resilient exactly when it is already in lowest terms, so the number of resilient fractions with denominator \(d\) is \(\varphi(d)\). Therefore the resilience of \(d\) is

$R(d)=\frac{\varphi(d)}{d-1}.$

The goal is to find the smallest denominator \(d\) such that

$R(d) \lt \frac{15499}{94744}.$

Brute force is a poor fit, because most denominators are obviously far from optimal. The successful approach is to search directly through the prime factorizations that can plausibly minimize \(d\).

Mathematical Approach

The decisive fact is that resilience is governed much more by the distinct prime divisors of \(d\) than by their exponents. The implementations are built around that separation.

From resilient fractions to the totient function

A numerator \(n\) gives a resilient fraction \(n/d\) precisely when \(\gcd(n,d)=1\). Among the \(d-1\) possible numerators \(1 \le n \lt d\), exactly \(\varphi(d)\) are coprime to \(d\). That turns the original counting problem into a purely multiplicative number-theory problem: once \(\varphi(d)\) is known, the resilience follows immediately.

Prime factorization separates the distinct primes from the exponents

If

$d=\prod_{i=1}^{k} p_i^{e_i},$

then Euler's product formula gives

$\varphi(d)=d\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)=\prod_{i=1}^{k} p_i^{e_i-1}(p_i-1).$

Hence

$R(d)=\frac{d}{d-1}\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right).$

This identity is the heart of the search. The product \(\prod (1-1/p_i)\) depends only on which primes divide \(d\), not on how large the exponents are. Raising an exponent does not change \(\varphi(d)/d\); it only replaces the prefactor \(d/(d-1)\) by a slightly smaller number that is closer to 1. So introducing a new distinct prime causes the main drop in resilience, while increasing an existing exponent is a fine-tuning move once the denominator is already close to the target.

This also explains why the search starts with the smallest primes. A new prime \(p\) multiplies \(\varphi(d)/d\) by \(1-1/p\), and that reduction is strongest for small \(p\). Minimal candidates therefore come from products of consecutive small primes, possibly followed by extra powers of those same primes.

Why only canonical exponent vectors need to be searched

Suppose two primes satisfy \(p \lt q\), and two exponents satisfy \(a \gt b\). Then

$p^a q^b \lt p^b q^a.$

So if a denominator uses the same two primes and the same two exponents, it is always smaller when the larger exponent is attached to the smaller prime. More generally, for a fixed set of primes and a fixed multiset of exponents, the smallest denominator is obtained when the exponents are non-increasing along the increasing prime list:

$e_1 \ge e_2 \ge e_3 \ge \cdots.$

That ordering is not merely a convenience. It is a correctness argument for the DFS: any candidate that breaks this rule can be rearranged into a smaller denominator with the same distinct-prime set, so it cannot be the minimal solution.

Exact comparison and a worked example

Instead of dividing, the implementations test the target inequality as

$\varphi(d)\cdot 94744 \lt 15499\cdot(d-1).$

This avoids floating-point rounding and keeps the search exact.

A small checkpoint illustrates the mechanism. If the threshold were \(4/10\), then \(d=6=2\cdot 3\) gives

$\varphi(6)=2,\qquad R(6)=\frac{2}{5}=\frac{4}{10},$

so the strict inequality still fails. But \(d=12=2^2\cdot 3\) gives

$\varphi(12)=4,\qquad R(12)=\frac{4}{11}\lt\frac{4}{10}.$

That is exactly the pattern exploited in the full problem: a squarefree product of small primes pushes the resilience down quickly, and then an extra power of a small prime can be the final adjustment that crosses the line with the smallest possible denominator.

How the Code Works

The C++, Python, and Java implementations perform a depth-first search over increasing primes. The state carried by the recursion is the current denominator \(d\), the current totient \(\varphi(d)\), the position in the prime list, the maximum exponent allowed for the next prime, and the best valid denominator found so far.

Incremental totient updates

The search never recomputes \(\varphi(d)\) from scratch. When a prime \(p\) is attached for the first time, the update is

$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)(p-1).$

If the same prime is extended from exponent \(e\) to exponent \(e+1\), the update becomes

$d \leftarrow dp,\qquad \varphi(d)\leftarrow \varphi(d)p.$

Those two rules are the main invariant of the recursion and come directly from the prime-power formula for \(\varphi\).

Why the search tree stays small

At each node, the implementation first checks whether the current denominator already meets the target. If it does, that denominator becomes the new global best and the branch stops, because multiplying by more primes can only increase \(d\). If the current denominator is already at least as large as the best known answer, the branch is also discarded immediately.

The next recursive call receives the current exponent as the upper bound for the next prime, enforcing the canonical condition \(e_1 \ge e_2 \ge \cdots\). This removes duplicate exponent permutations automatically. The implementations only need a short initial list of consecutive primes, up to 31, because the optimum is found inside that heavily pruned search space. The C++ implementation widens the cross-multiplication to 128-bit integer arithmetic, Python uses arbitrary-precision integers, and Java remains safely within 64-bit range for this target.

Complexity Analysis

Without pruning, the problem is combinatorial in the possible exponent vectors. A useful way to describe the explored set is: the DFS visits only tuples

$e_1 \ge e_2 \ge \cdots \ge 0,\qquad \prod_i p_i^{e_i} \lt d_{\text{best}},$

where \(d_{\text{best}}\) is the best denominator known at that stage of the search. The exponent-order restriction removes all reorderings of the same multiset, and the best-value bound cuts off large branches before they expand.

Memory usage is \(O(k)\), where \(k\) is the recursion depth, because only one search path is stored at a time. For the actual target, \(k\) is a small constant and the visited tree is tiny in practice. The algorithm is fast precisely because it searches near-optimal factorizations instead of scanning all integers.

Footnotes and References

1. Project Euler problem page: Problem 243 - Resilience
2. Euler totient function: Wikipedia - Euler's totient function
3. Coprime integers: Wikipedia - Coprime integers
4. Primorials and products of the smallest primes: Wikipedia - Primorial
5. Branch and bound: Wikipedia - Branch and bound