Problem 243: Resilience

Detailed mathematical approach

Problem Summary

A proper fraction is a positive fraction whose numerator is smaller than its denominator, so a denominator \(d\) has the \(d-1\) proper fractions \(1/d,2/d,\dots,(d-1)/d\). A fraction is resilient if it cannot be cancelled down, and the resilience \(R(d)\) is the ratio of the proper fractions of \(d\) that are resilient. For \(d=12\) the resilient ones are \(1/12\), \(5/12\), \(7/12\) and \(11/12\), so \(R(12)=4/11\), and \(12\) is the smallest denominator with \(R(d)\lt4/10\). We must find the smallest denominator \(d\) with \(R(d)\lt15499/94744\). ^[1]

The whole solution in one sentence: the resilience is Euler's totient \(\varphi(d)\) divided by \(d-1\), which falls below \(15499/94744\) only if \(d\) is divisible by all nine primes from \(2\) to \(23\) or has even more prime factors, and a short search with exact integer comparisons finds the smallest such \(d\) that works.

Mathematical Approach

We count the resilient fractions with Euler's totient and split the resilience into a prime part, which decides how many prime factors \(d\) needs, and a size part, which decides which multiple of their product works first.

1. Resilient fractions are counted by the totient

A fraction \(n/d\) can be cancelled down exactly when \(n\) and \(d\) have a common divisor greater than \(1\), so it is resilient exactly when \(\gcd(n,d)=1\), that is, when it is in lowest terms. ^[2] For \(d=12\) the numerators \(2,3,4,6,8,9,10\) share the factor \(2\) or \(3\) with \(12\), as in \(9/12=3/4\), and only \(1,5,7,11\) remain. The number of integers \(1\le n\le d\) with \(\gcd(n,d)=1\) is Euler's totient \(\varphi(d)\). ^[3] For \(d\ge2\) the integer \(n=d\) is not among them, so all of them are numerators of proper fractions, and

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

2. Small denominators

For \(d=2,\dots,12\) this gives \(R(2)=R(3)=1\), \(R(4)=2/3\), \(R(5)=1\), \(R(6)=2/5\), \(R(7)=1\), \(R(8)=4/7\), \(R(9)=3/4\), \(R(10)=4/9\), \(R(11)=1\) and \(R(12)=4/11\). The value \(R(6)=2/5\) equals \(4/10\), so \(6\) just misses the strict inequality, and \(12\) is the first denominator below \(4/10\), as the statement says. The two smallest values belong to \(6\) and \(12\), the only numbers here divisible by both \(2\) and \(3\); the next sections show why.

3. Euler's product formula

Let \(q_1,\dots,q_k\) be the different primes dividing \(d\), and for a set \(S\) of them let \(D_S\) be their product, with \(D_S=1\) for the empty set. Since \(D_S\) divides \(d\), exactly \(d/D_S\) of the numbers \(1,\dots,d\) are multiples of \(D_S\), that is, divisible by every prime of \(S\). The numbers coprime to \(d\) are those divisible by none of the \(q_i\), and the inclusion–exclusion principle counts them by adding the counts \(d/D_S\) with the sign \((-1)^{|S|}\): ^[4]

$$\begin{aligned}\varphi(d)&=\sum_{S}(-1)^{|S|}\,\frac{d}{D_S}\\&=d\prod_{i=1}^{k}\Bigl(1-\frac1{q_i}\Bigr).\end{aligned}$$

Multiplying out the product in the second line gives the sum in the first. For \(d=12\) the sum is \(12-6-4+2=4\): the multiples of \(2\) and of \(3\) are removed, and the two multiples of \(6\), removed twice, are put back once. Dividing by \(d-1\),

$$\begin{aligned}R(d)&=\frac{d}{d-1}\cdot P(d),\\P(d)&=\prod_{p\mid d}\Bigl(1-\frac1p\Bigr).\end{aligned}$$

We call \(P(d)=\varphi(d)/d\) the prime part; it depends only on which primes divide \(d\), not on how often. The size part \(d/(d-1)\) is larger than \(1\) and comes closer to \(1\) as \(d\) grows. For example, \(6\), \(12\) and \(18\) share the prime part \(1/3\), and their resiliences \(2/5\), \(4/11\) and \(6/17\) shrink toward it.

4. Many small primes make the prime part small

Write \(p_1=2\), \(p_2=3\), \(p_3=5\), … for the primes in increasing order and \(p_k\#=p_1p_2\cdots p_k\) for the primorial, the product of the first \(k\) primes, ^[5] whose prime part is

$$r_k=\prod_{i=1}^{k}\Bigl(1-\frac1{p_i}\Bigr)=\frac{\varphi(p_k\#)}{p_k\#}.$$

Claim. If \(d\) has exactly \(k\) different prime factors, then \(P(d)\ge r_k\) and \(d\ge p_k\#\).

Proof. List the prime factors as \(q_1\lt q_2\lt\dots\lt q_k\). The prime \(q_i\) is larger than the \(i-1\) primes \(q_1,\dots,q_{i-1}\), so it is at least the \(i\)-th prime: \(q_i\ge p_i\). Since \(1-1/x\) grows with \(x\), each factor \(1-1/q_i\) of \(P(d)\) is at least \(1-1/p_i\), and \(d\ge q_1q_2\cdots q_k\ge p_k\#\). \(\square\)

So \(\varphi(n)/n\) is smaller at a primorial than at any smaller positive integer. ^[5] The first values are \(r_1=1/2\), \(r_2=1/3\), \(r_3=4/15\), \(r_4=8/35\), \(r_5=16/77\) and, rounded, \(r_6\approx0.19181\), \(r_7\approx0.18053\), \(r_8\approx0.17102\), \(r_9\approx0.16359\) and \(r_{10}\approx0.15795\).

5. The threshold needs nine prime factors

Let \(t=15499/94744\approx0.16359\), and let \(\omega(d)\) be the number of different prime factors of \(d\). The size part is larger than \(1\), so Section 4 gives

$$R(d)\gt P(d)\ge r_{\omega(d)}.$$

Since \(r_8\approx0.17102\gt t\), every \(d\) with \(R(d)\lt t\) has at least nine different prime factors, and then \(d\ge p_9\#=23\#=223092870\). With nine primes the prime part can just get below \(t\): \(r_9\lt t\), but the two numbers agree in their first nine decimal places. The denominator \(23\#\) itself still fails; its size part is a little too large.

6. Nine prime factors must be the primes up to 23

Suppose \(d\) has exactly nine different prime factors \(q_1\lt\dots\lt q_9\), but they are not \(2,3,5,\dots,23\). Then \(q_9\ge29\), because nine different primes up to \(23\) would be all of them, and \(q_i\ge p_i\) for \(i\le8\) as in Section 4. Hence

$$\begin{aligned}P(d)&\ge r_8\Bigl(1-\frac1{29}\Bigr)=\frac{221184}{1339481}\\&\approx0.16513\gt t,\end{aligned}$$

and \(d\) fails. A solution with nine prime factors is therefore \(d=23\#\cdot m\), where the cofactor \(m\ge1\) has no prime factor above \(23\) and the prime part is exactly \(r_9\).

7. The size part decides

For these \(d\) the resilience \(R(d)=r_9\,d/(d-1)\) falls as \(d\) grows. The condition \(R(d)\lt t\) reads \(r_9\,d\lt t\,(d-1)\), that is, \(d\,(t-r_9)\gt t\), and because \(t\gt r_9\) it becomes

$$d\gt B=\frac{t}{t-r_9}.$$

So the nine-prime solutions are the numbers \(23\#\cdot m\) above \(B\), and the smallest is \(23\#\cdot m^{*}\), where \(m^{*}\) is the smallest number without prime factors above \(23\) such that \(23\#\cdot m^{*}\gt B\).

8. Ten or more prime factors

A number with at least ten different prime factors is at least \(p_{10}\#=29\#=6469693230\) by Section 4, and \(29\#\) itself works:

$$R(29\#)=\frac{1021870080}{6469693229}\approx0.15795\lt t.$$

Claim. The smallest \(d\) with \(R(d)\lt t\) is the smaller of \(23\#\cdot m^{*}\) and \(29\#\).

This follows from Sections 5 to 7 and the two facts above. Every integer from \(1\) to \(28\) has only prime factors up to \(23\), so if \(23\#\cdot m^{*}\lt29\#\), then \(m^{*}\) is simply the first integer with \(23\#\cdot m^{*}\gt B\); an exact computation with fractions shows that this is the case here.

9. Worked example: the threshold 4/10

The same steps reproduce the example of the statement, \(t=2/5\). Here \(r_1=1/2\ge t\) and \(r_2=1/3\lt t\), so \(d\) needs at least two prime factors. If it has exactly two and they are not \(2\) and \(3\), the larger is at least \(5\), so \(P(d)\ge\frac12\cdot\frac45=t\), which fails because \(R(d)\gt P(d)\). So \(d=6m\) with \(m\) built from \(2\) and \(3\), and

$$B=\frac{2/5}{2/5-1/3}=\frac{2/5}{1/15}=6.$$

The first multiple of \(6\) above \(6\) is \(12\), with \(R(12)=4/11\lt2/5\), while three or more prime factors need \(d\ge30\). So the answer is \(12\), as stated.

10. Worked example: the threshold 27/100

For \(t=27/100\) the same steps lead to an answer in which \(3\) has a larger exponent than \(2\). Now \(r_2=1/3\gt t\) and \(r_3=4/15\lt t\), so \(d\) needs at least three prime factors, and three other than \(2,3,5\) include one of at least \(7\), so \(P(d)\ge\frac12\cdot\frac23\cdot\frac67\)\({}=\frac27\gt t\). Hence \(d=30m\) with \(m\) built from \(2\), \(3\) and \(5\). From \(t-r_3=1/300\) we get \(B=81\). The multiple \(60\) is too small, \(R(60)=16/59\approx0.2712\), but \(90=2\cdot3^2\cdot5\) works: \(R(90)=24/89\approx0.2697\). Four or more prime factors need \(d\ge210\), so the answer is \(90\).

11. The numbers the program tries

Among all numbers with the same exponents, the smallest gives the largest exponent to \(2\), the next to \(3\), and so on, because for primes \(p\lt q\) and exponents \(a\gt b\)

$$\frac{p^a q^b}{p^b q^a}=\Bigl(\frac pq\Bigr)^{a-b}\lt1.$$

The numbers \(2^{e_1}3^{e_2}5^{e_3}\cdots\) with \(e_1\ge e_2\ge e_3\ge\dots\) are exactly the products of primorials. If \(e_k\) is the last positive exponent and \(e_{k+1}=0\), such a number is the product of \(e_j-e_{j+1}\) copies of \(p_j\#\) for \(j=1,\dots,k\), as in \(12=2\cdot6\) and \(360=2\cdot6\cdot30\); conversely, a primorial that contains a prime contains all smaller primes. These numbers begin \(1,2,4,6,8,12,16,24,30,\dots\) ^[6] The published programs try only these numbers. That is natural but not automatically safe, because moving larger exponents to smaller primes makes \(d\) smaller and its size part larger. For \(t=27/100\) the programs find \(120=2^3\cdot3\cdot5\), with \(R(120)=32/119\), instead of \(90\). Even \(t=4/11\) goes wrong: the answer is \(18=2\cdot3^2\), with \(R(18)=6/17\), but its rearrangement \(12\) has \(R(12)=4/11\), not less, and the programs return \(24=2^3\cdot3\).

For the threshold of this problem the restriction does no harm. The exact computation of Section 8 gives \(m^{*}\lt29\), so the answer is \(23\#\cdot m^{*}\), and it also shows that the exponents of \(m^{*}\) at \(2,3,5,\dots,23\), with \(0\) for absent primes, are non-increasing. Adding \(1\) to each gives the exponents of \(23\#\cdot m^{*}\), so the answer is a product of primorials, and by Section 12 the search finds it.

12. A search with a running record

The search builds the products of primorials prime by prime: from \(1\) it multiplies by \(2^{e_1}\), then by \(3^{e_2}\) with \(1\le e_2\le e_1\), and so on, keeping the smallest working number found so far, the record. This is a depth-first branch and bound, which drops a branch once it cannot beat the record. ^[7] A number at least as large as the record is dropped with all its extensions; a working number becomes the record and is not extended; and the exponent of the current prime stops growing once the number would exceed the record. Everything skipped is thus at least the record of its moment or a multiple of a smaller working number, so the search returns the smallest working product of primorials of its primes.

Multiplying \(n\) by a new prime \(p\) multiplies the prime part by \(1-1/p\), so \(\varphi\) is multiplied by \(p-1\); multiplying by a prime that already divides \(n\) leaves the prime part alone, so \(\varphi\) is multiplied by \(p\). The test \(R(n)\lt t\) uses integers only:

$$\varphi(n)\cdot94744\lt15499\cdot(n-1).$$

For the checkpoint \(4/10\) the search makes seven calls: \(1\to2\to6\to30\), where \(R(30)=8/29\lt2/5\) is the first record; then \(4\) and the new record \(12\); then \(8\), after which \(8\cdot3=24\) and \(2^4=16\) would exceed the record. For the real threshold the first branch runs through the primorials and makes \(29\#\) the first record at the eleventh call; the whole search makes \(1249\) calls.

How the Code Works

In the C++ program, ^[8] parse_arguments reads the options --target-num= and --target-den=, which replace the default threshold \(15499/94744\), and --skip-checkpoints; numbers are read as unsigned 64-bit integers without an overflow check, so a value of \(2^{64}\) or more wraps around, and an unknown argument or a zero denominator ends the program with exit code \(1\). Unless skipped, run_checkpoints requires solve(4, 10) to return \(12\), the example of the statement, or ends the program with exit code \(2\). Then main prints solve for the threshold.

solve keeps the eleven primes \(2,\dots,31\) in a vector and the record in best, which starts at \(2^{64}-1\). The search of Section 12 is the recursive lambda dfs; it receives itself as its first argument, then the index prime_index of the next prime, the largest exponent max_exp that prime may get, the current number n and its totient phi_n. A call returns if n >= best; it sets best = n and returns if \(n\gt1\) and resilience_less_than reports \(R(n)\lt t\); and it returns when all eleven primes are used. Otherwise a loop over exp from \(1\) to max_exp multiplies n_mul by the next prime \(p\), phi_mul by \(p-1\) the first time and by \(p\) after that, and calls dfs for the next prime with max_exp = exp, which keeps the exponents non-increasing. The loop stops when n_mul > best / p, which with integer division is the same as n_mul * p > best but cannot overflow, so although the first call dfs(dfs, 0U, 64, 1, 1) allows \(64\) factors \(2\), every product stays below \(2^{64}\). resilience_less_than forms both sides of the test of Section 12 as unsigned 128-bit products, ^[9] exact for all 64-bit inputs.

For any threshold the result is right exactly when the answer is a product of primorials of primes up to \(31\) below \(2^{64}\), as Section 11 shows it is here: for \(t=27/100\) the program prints \(120\), and for \(t\le r_{11}\approx0.15285\) it prints the unchanged start value \(2^{64}-1\).

The Python solve(target_num=15499, target_den=94744) has the same structure, with a nested dfs, the record in a one-element list best that dfs can change, and unbounded integers. ^[9] Its record starts as float('inf'), so best[0] // p is nan and the guard stays false until the first record; this is harmless, because the first branch sets the record \(29\#\) before any exponent above \(1\) is tried. It returns the result as a string. The Java program uses static fields and long: every number the search visits is at most \(29\#\lt6.5\cdot10^9\), so both sides of the test stay below \(10^{15}\), far below \(2^{63}-1\). Neither has options or a checkpoint.

Complexity and Verification

The search makes \(1249\) calls for this threshold. Apart from its loop, a call does a fixed amount of work, and each pass of the loop starts a call or ends the loop, so the time is proportional to the number of calls. They are bounded by the \(1809\) products of primorials up to the first record \(29\#\), counting \(1\); the shrinking record skips about a third of them. The recursion is at most \(12\) calls deep, so the memory is constant. On the test machine (GCC 16 with -O2, OpenJDK 17, Python 3.11) each program runs in at most a few hundredths of a second, almost all of it start-up time, whereas testing every \(d\) up to \(23\#\) alone would take more than \(2\cdot10^8\) totients.

The C++ program checks itself with the checkpoint \(4/10\), and all three programs print the same number. For this article three independent checks were run, none of them part of the published solutions. First, the case analysis of Sections 5 to 8, evaluated with exact fractions, gives the same denominator, and its \(m^{*}\) has non-increasing exponents. Second, all \(9726\) numbers below \(29\#\) with at least nine different prime factors, with any primes and exponents, were tested exactly: the smallest that works is again the same, and every one that works is a multiple of \(23\#\); with Section 5 this covers every \(d\lt29\#\). Third, for the \(3475\) fractions \(t=a/b\) in lowest terms with \(b\le120\) and \(16/77\lt t\lt1\), a sieve of \(\varphi(d)\) up to \(10^6\) gave the true answers. The case analysis is right in all \(1185\) cases where Section 6 fixes the primes; the published search, in Python and in C++, is wrong for \(60\) thresholds, such as \(4/11\), \(5/14\), \(9/25\) and \(27/100\), always with a true answer \(18\), \(90\), \(150=2\cdot3\cdot5^2\) or \(1050=2\cdot3\cdot5^2\cdot7\) that has a larger exponent on a larger prime.

Footnotes and References

The references below supply the background facts used above; the split into prime part and size part, the case analysis and all numbers in the examples are derived or computed in this article.

1. Project Euler 243 — Resilience. The official statement defines proper fractions, resilient fractions as those that cannot be cancelled down, and the resilience R(d); it gives R(12) = 4/11, notes that 12 is the smallest denominator with R(d) < 4/10, and asks for the smallest denominator d with R(d) < 15499/94744.
2. Wikipedia — Irreducible fraction. A fraction is in lowest terms when its numerator and denominator have no common divisor other than 1, that is, exactly when they are coprime.
3. Wikipedia — Euler's totient function. φ(n) counts the integers 1 ≤ k ≤ n with gcd(n, k) = 1, and Euler's product formula gives φ(n) = n ∏ (1 − 1/p) over the distinct primes p dividing n.
4. Wikipedia — Inclusion–exclusion principle. The principle counts the elements in none of several finite sets by an alternating sum over their intersections, and its section on Euler's phi function derives φ(n) = n − Σ n/pᵢ + Σ n/(pᵢpⱼ) − ⋯ = n ∏ (1 − 1/pᵢ).
5. Wikipedia — Primorial. The primorial pₙ# is the product of the first n primes, with the values 2, 6, 30, 210, 2310, …, 223092870, 6469693230; for every primorial n the fraction φ(n)/n is smaller than for any positive integer less than n.
6. OEIS A025487 — Least integer of each prime signature; also products of primorial numbers. The sequence consists of all numbers 2^k₁ · 3^k₂ ⋯ pₙ^kₙ with k₁ ≥ k₂ ≥ ⋯ ≥ kₙ and begins 1, 2, 4, 6, 8, 12, 16, 24, 30, …
7. Wikipedia — Branch and bound. A part of the search space is discarded if it cannot produce a better solution than the best one found so far, and a depth-first order quickly produces complete solutions and therefore bounds.
8. C++ — Euler243.cpp. The linked immutable revision contains parse_arguments, resilience_less_than, solve with its recursive search and run_checkpoints. It is the implementation record for this article.
9. GCC manual — 128-bit Integers documents unsigned __int128, written __uint128_t in the program; Java — Primitive Data Types gives the range −2⁶³ to 2⁶³ − 1 of long; Python — numeric types states that integers have unlimited precision.