Project Euler

Resilience

For a denominator d > 1, the resilience is defined as R(d) = (phi(d))/(d - 1) where phi is Euler's totient function. Find the smallest d such that R(d) < dfrac1549994744.

Source sync Apr 19, 2026

Problem #0243

Level Level 04

Solved By 10,512

Languages C++, Python

Answer 892371480

Length 303 words

number_theorysearchmodular_arithmetic

A positive fraction whose numerator is less than its denominator is called a proper fraction.

For any denominator, $d$, there will be $d - 1$ proper fractions; for example, with $d = 12$:

$1 / 12, 2 / 12, 3 / 12, 4 / 12, 5 / 12, 6 / 12, 7 / 12, 8 / 12, 9 / 12, 10 / 12, 11 / 12$.

We shall call a fraction that cannot be cancelled down a resilient fraction.

Furthermore we shall define the resilience of a denominator, $R(d)$, to be the ratio of its proper fractions that are resilient; for example, $R(12) = 4/11$.

In fact, $d = 12$ is the smallest denominator having a resilience $R(d) < 4/10$.

Find the smallest denominator $d$, having a resilience $R(d) < 15499/94744$.

Problem 243: Resilience

Mathematical Foundation

Theorem 1 (Resilience via Euler’s product). For any integer $d > 1$ ,

R(d) = \frac{d}{d-1} \prod_{p \mid d} \left(1 - \frac{1}{p}\right).

Proof. By Euler’s product formula, $\phi(d) = d \prod_{p \mid d}(1 - 1/p)$ . Dividing by $d - 1$ yields the result. $\square$

Lemma 1 (Primorial optimality). Let $P_k = \prod_{i=1}^{k} p_i$ be the product of the first $k$ primes (the $k$ -th primorial). Among all integers with exactly $k$ distinct prime factors, $P_k$ minimises $\prod_{p \mid d}(1 - 1/p)$ .

Proof. The function $p \mapsto 1 - 1/p$ is strictly increasing for primes. If $d$ has $k$ distinct prime factors $q_1 < \cdots < q_k$ , then $q_i \ge p_i$ for each $i$ , so $\prod(1 - 1/q_i) \ge \prod(1 - 1/p_i)$ , with equality iff $q_i = p_i$ for all $i$ . $\square$

Theorem 2 (Search reduction). The smallest $d$ with $R(d) < r$ has the form $d = m \cdot P_k$ for some $k$ and some integer $m \ge 1$ whose prime factors are among $\{p_1, \ldots, p_k\}$ .

Proof. Suppose $d$ is the smallest solution. Write $d = \prod p_i^{a_i}$ with distinct primes $q_1 < \cdots < q_s$ . If $q_i > p_i$ for some $i$ , replacing $q_i$ by $p_i$ would decrease $\prod(1-1/p)$ and decrease or maintain $d/(d-1)$ (since the replacement cannot increase $d$ ), yielding a smaller or equal solution. Hence the primes of $d$ must be exactly $\{p_1, \ldots, p_k\}$ for some $k$ , and $d = m \cdot P_k$ where $m$ divides a product of powers of $p_1, \ldots, p_k$ . $\square$

Lemma 2 (Multiplier bound). For $d = m \cdot P_k$ with $m \mid P_k^\infty$ (i.e., $m$ has no prime factors outside $\{p_1,\ldots,p_k\}$ ):

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

Thus $R(d) < r$ iff $m \cdot P_k > \dfrac{\prod(1-1/p_i)}{r - \prod(1-1/p_i)}$ , giving an explicit lower bound on $m \cdot P_k$ .

Proof. Since $m$ introduces no new prime factors, $\phi(m \cdot P_k) = m \cdot P_k \prod_{i=1}^k (1 - 1/p_i)$ . Dividing by $m \cdot P_k - 1$ gives the formula. Rearranging $R(d) < r$ yields the stated bound. $\square$

Editorial

Strategy: 1. The ratio phi(d)/d = prod(1 - 1/p) for p | d is minimized by primorial numbers. 2. Find the first primorial P_k with R(P_k) < target. 3. Search d = m * P_j for j < k and small multipliers m. We check if P itself satisfies the bound. We then p_k works; but a smaller multiple of P_{k-1} might also work. Finally, search d = m * P_{k-1} for m = 2, 3, … (only smooth m).

Pseudocode

Check if P itself satisfies the bound
P_k works; but a smaller multiple of P_{k-1} might also work
We already checked P_{k-1} and it failed, so search
multiples m * P_{k-1}
Search d = m * P_{k-1} for m = 2, 3, ... (only smooth m)
Compute R(d) using Euler's product

Complexity Analysis

Time: $O(k + M)$ where $k$ is the primorial index (at most 10-15) and $M$ is the number of multipliers tested (bounded by $P_k / P_{k-1} = p_k$ , a small prime). Total: $O(p_k) = O(1)$ in practice.
Space: $O(1)$ .

Answer

\boxed{892371480}

C++ project_euler/problem_243/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 243: Resilience
 *
 * Find the smallest d such that phi(d)/(d-1) < 15499/94744.
 *
 * Strategy:
 * 1. Compute primorials P_k = 2*3*5*...*p_k
 * 2. For each k, check if R(P_k) < target.
 * 3. Once P_k overshoots, for k-1 try d = m * P_{k-1} for m = 1, 2, ...
 *    and find the smallest d satisfying the inequality.
 *
 * For d = m * P_k where gcd(m, P_k) = g:
 *   phi(d) = phi(m) * phi(P_k) * g / phi(g)
 *
 * If m divides P_k (i.e., m is a product of primes in P_k), then:
 *   phi(m * P_k) = m * P_k * prod_{p | P_k}(1 - 1/p) = m * phi(P_k)
 *   (since m*P_k has the same prime factors as P_k when m | P_k^inf)
 *
 * Actually more precisely: if m's prime factors are all among those of P_k, then
 *   phi(m * P_k) = m * phi(P_k) (since the set of prime factors doesn't change,
 *   and phi(n) = n * prod(1 - 1/p))... wait, that's only true if m is a prime power
 *   of existing primes. In general:
 *   phi(m * P_k) = (m * P_k) * prod_{p | (m * P_k)} (1 - 1/p)
 *   If rad(m) | P_k, then the prime set is the same, so:
 *   phi(m * P_k) = m * P_k * prod_{p | P_k}(1-1/p) = m * phi(P_k).
 */

typedef long long ll;
typedef __int128 lll;

int main() {
    ios_base::sync_with_stdio(false);

    // Target: 15499/94744
    ll target_num = 15499;
    ll target_den = 94744;

    // Primes
    vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};

    // Compute primorials and their totients
    // P_k, phi(P_k)
    vector<ll> primorial(1, 1), phi_primorial(1, 1);

    for (int i = 0; i < (int)primes.size(); i++) {
        int p = primes[i];
        primorial.push_back(primorial.back() * p);
        phi_primorial.push_back(phi_primorial.back() * (p - 1));
    }

    // For each k, check if R(P_k) < target, i.e., phi(P_k) * target_den < target_num * (P_k - 1)
    // Find the first k where R(P_k) < target
    int first_k = -1;
    for (int k = 1; k <= (int)primes.size(); k++) {
        ll pk = primorial[k];
        ll phik = phi_primorial[k];
        // Check phik / (pk - 1) < target_num / target_den
        // i.e., phik * target_den < target_num * (pk - 1)
        // Use __int128 to avoid overflow
        lll lhs = (lll)phik * target_den;
        lll rhs = (lll)target_num * (pk - 1);
        if (lhs < rhs) {
            first_k = k;
            break;
        }
    }

    // Now try d = m * P_{k-1} for increasing m, where m's prime factors
    // are all <= p_{k-1} (the primes in P_{k-1}).
    // Also try d = m * P_{k-2}, etc.
    // We want the globally smallest d.

    ll best_d = primorial[first_k]; // This works, but may not be smallest

    // Try for each base primorial P_j where j < first_k
    for (int j = 1; j < first_k; j++) {
        ll pj = primorial[j];
        ll phij = phi_primorial[j];

        // d = m * pj, phi(d) depends on m's factorization
        // If m's prime factors are subset of primes in P_j:
        //   phi(d) = m * phij
        //   R(d) = m * phij / (m * pj - 1) < target_num / target_den
        //   m * phij * target_den < target_num * (m * pj - 1)
        //   m * phij * target_den < target_num * m * pj - target_num
        //   m * (phij * target_den - target_num * pj) < -target_num
        //   Since phij * target_den - target_num * pj < 0 (because R(P_j) > target for j < first_k):
        //   m > target_num / (target_num * pj - phij * target_den)

        lll denom = (lll)target_num * pj - (lll)phij * target_den;
        if (denom <= 0) continue;

        // m > target_num / denom
        ll m_min = (ll)(target_num / (long long)denom) + 1;

        // But m must have all prime factors in P_j's primes.
        // The smallest such m >= m_min: could be m_min if it's smooth w.r.t. P_j's primes,
        // or we need to search.

        // Generate smooth numbers (all prime factors <= primes[j-1]) near m_min
        // Actually, m can also introduce NEW primes, but then phi(d) changes.
        // Let's handle both cases.

        // Case 1: m smooth w.r.t. P_j
        // Find smallest smooth m >= m_min
        // Use BFS/priority queue to generate smooth numbers
        {
            // For small m_min, just check each m
            if (m_min <= 1000000) {
                for (ll m = max(m_min, 2LL); m <= 1000000; m++) {
                    // Check if m is smooth w.r.t. primes[0..j-1]
                    ll t = m;
                    bool smooth = true;
                    for (int i = 0; i < j; i++) {
                        while (t % primes[i] == 0) t /= primes[i];
                    }
                    if (t != 1) smooth = false;
                    if (smooth) {
                        ll d = m * pj;
                        if (d < best_d) {
                            best_d = d;
                        }
                        break; // smallest smooth m found
                    }
                }
            }
        }

        // Case 2: m introduces exactly one new prime p (not in P_j)
        // Then d = m * pj has prime factors = P_j's primes union {p}
        // phi(d) = d * prod_{q | d}(1 - 1/q)
        //        = m * pj * prod_{q in P_j}(1-1/q) * (1-1/p)
        //        = m * phij * (1 - 1/p)
        //        = m * phij * (p-1)/p
        // R(d) = m * phij * (p-1) / (p * (m*pj - 1))
        // We want this < target_num / target_den
        // m * phij * (p-1) * target_den < target_num * p * (m * pj - 1)
        // m * (phij * (p-1) * target_den - target_num * p * pj) < -target_num * p
        // If the coefficient of m is negative:
        // m > target_num * p / (target_num * p * pj - phij * (p-1) * target_den)

        for (int pi = j; pi < (int)primes.size() && pi < j + 5; pi++) {
            int p = primes[pi];
            if (pi < j) continue; // already in P_j

            lll coeff = (lll)target_num * p * pj - (lll)phij * (p-1) * target_den;
            if (coeff <= 0) continue;

            ll m_min2 = (ll)((lll)target_num * p / coeff) + 1;

            // m must be of form p^a * (smooth w.r.t. P_j), with a >= 1
            // Smallest: m = p
            if (p >= m_min2) {
                ll d = (ll)p * pj;
                if (d < best_d) best_d = d;
            } else {
                // Try m = p * s for small smooth s
                for (ll s = 1; s <= 10000; s++) {
                    ll t = s;
                    bool smooth = true;
                    for (int i = 0; i < j; i++) {
                        while (t % primes[i] == 0) t /= primes[i];
                    }
                    if (t != 1) smooth = false;
                    if (!smooth) continue;

                    ll m = s * p;
                    if (m >= m_min2) {
                        ll d = m * pj;
                        if (d < best_d) best_d = d;
                        break;
                    }
                }
            }
        }
    }

    cout << best_d << endl;
    return 0;
}

Python project_euler/problem_243/solution.py

"""
Problem 243: Resilience

Find the smallest d such that phi(d)/(d-1) < 15499/94744.

Strategy:
1. The ratio phi(d)/d = prod(1 - 1/p) for p | d is minimized by primorial numbers.
2. Find the first primorial P_k with R(P_k) < target.
3. Search d = m * P_j for j < k and small multipliers m.
"""

from fractions import Fraction
from sympy import totient, factorint, primerange

target = Fraction(15499, 94744)

primes = list(primerange(2, 100))

# Compute primorials
primorials = [1]
phi_primorials = [1]
for p in primes:
    primorials.append(primorials[-1] * p)
    phi_primorials.append(phi_primorials[-1] * (p - 1))

# Find first k where R(P_k) < target
first_k = None
for k in range(1, len(primorials)):
    pk = primorials[k]
    phik = phi_primorials[k]
    if Fraction(phik, pk - 1) < target:
        first_k = k
        break

print(f"First primorial below target: P_{first_k} = {primorials[first_k]}")

best_d = primorials[first_k]

# Try d = m * P_j for j < first_k
for j in range(1, first_k):
    pj = primorials[j]
    phij = phi_primorials[j]
    prime_set = set(primes[:j])

    # Case 1: m is smooth w.r.t. P_j's primes
    # phi(m * pj) = m * phij (same prime factors)
    # Need m * phij / (m * pj - 1) < target
    # m * phij * target.denominator < target.numerator * (m * pj - 1)
    # m * (phij * target.den - target.num * pj) < -target.num
    denom = target.numerator * pj - phij * target.denominator
    if denom > 0:
        m_min = target.numerator // denom + 1

        # Find smallest smooth number >= m_min
        for m in range(max(int(m_min), 2), max(int(m_min), 2) + 2000000):
            t = m
            for p in primes[:j]:
                while t % p == 0:
                    t //= p
            if t == 1:
                d = m * pj
                if d < best_d:
                    best_d = d
                    print(f"  Found d = {m} * {pj} = {d} (smooth, j={j})")
                break

    # Case 2: m introduces one new prime
    for pi in range(j, min(j + 6, len(primes))):
        p = primes[pi]
        # phi(d) = m * phij * (p-1)/p  when m = p * s (s smooth)
        # R(d) = m * phij * (p-1) / (p * (m*pj - 1)) < target
        coeff = target.numerator * p * pj - phij * (p - 1) * target.denominator
        if coeff <= 0:
            continue
        m_min2 = target.numerator * p // coeff + 1

        # m must be p * s where s is P_j-smooth, s >= ceil(m_min2 / p)
        s_min = max(1, (int(m_min2) + p - 1) // p)
        for s in range(s_min, s_min + 2000000):
            t = s
            for q in primes[:j]:
                while t % q == 0:
                    t //= q
            if t == 1:
                m = s * p
                d = m * pj
                if d < best_d:
                    best_d = d
                    print(f"  Found d = {m} * {pj} = {d} (new prime {p}, j={j})")
                break

print(f"\nAnswer: {best_d}")