notes.html

problem 69 · 21 lines

<article>
<h3>Problem Analysis</h3>
<p>
The engine of this problem is <a class="reference-source" href="https://en.wikipedia.org/wiki/Euler%27s_totient_function" rel="noopener noreferrer" target="_blank">Euler's totient function</a>, written phi(n), which counts the positive integers up to n that are <a class="reference-source" href="https://en.wikipedia.org/wiki/Coprime_integers" rel="noopener noreferrer" target="_blank">coprime</a> to n - that is, share no common divisor with n greater than 1. The function has a clean closed form built from n's distinct prime factors. If n's distinct primes are p1, p2, ..., pk (their exponents do not matter here), then phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk). The exponents drop out of the product of fractions entirely - only the *set* of distinct primes dividing n appears.
</p>
<p>
We want to maximise the ratio n/phi(n). Dividing the formula above through by phi gives n/phi(n) = product over distinct primes p dividing n of p/(p-1). This factorisation is the whole game. Every factor p/(p-1) is strictly greater than 1, so adding any new distinct prime strictly *increases* the ratio. Repeating a prime adds nothing to the ratio (only distinct primes count) while still inflating n, so we never raise a prime above the first power. And the factor p/(p-1) is largest for the smallest primes - 2/1 = 2, then 3/2 = 1.5, then 5/4 = 1.25 - shrinking towards 1 as p grows. To extract the most ratio per unit of n, we therefore multiply together consecutive primes starting at 2. The maximiser is always a <a class="reference-source" href="https://en.wikipedia.org/wiki/Primorial" rel="noopener noreferrer" target="_blank">primorial</a>: the product of the first k primes, for the largest k whose product fits under the bound. This collapses an apparent million-element search into roughly seven multiplications, since 2*3*5*7*11*13*17*19*23 already exceeds a billion. The work is effectively O(1) in the bound.
</p>
<h3>Solution Approach</h3>
<h4>Greedy Primorial Accumulation</h4>
<p>
Both the C and Python files implement the same idea: keep a running product, start it at 1, and multiply in successive primes for as long as the product stays within the limit. The moment the next prime would push us over, we stop, and the last in-bounds product is the answer. Given the analysis above, this greedy march is provably optimal - because the smallest primes give the biggest factors and each distinct prime helps, the dense-as-possible primorial under the bound is the unique maximiser.
</p>
<p>
The two versions differ only in how they source primes and how they handle the boundary. The C solution uses <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a>: for each candidate it tests divisibility by odd numbers up to its square root. Because we need fewer than ten primes, this inner loop is trivially cheap and needs no array allocation. Crucially, the C code follows a *validate-then-commit* discipline. It computes the tentative product in a local <code>next = result * candidate</code> and only writes it back into <code>result</code> when <code>next</code> is confirmed to be at or below the limit. If it overshoots, we break immediately with <code>result</code> untouched. There is no rollback to get wrong.
</p>
<p>
The Python solution sources its primes from <code>primes_generator</code>, a lazy infinite <a class="reference-source" href="https://docs.python.org/3/glossary.html#term-generator" rel="noopener noreferrer" target="_blank">generator</a> built around an incremental <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a>. Instead of a fixed boolean array, it keeps a dictionary <code>composites</code> mapping each "next composite to be struck" back to the prime that strikes it. When a candidate odd <code>n</code> is absent from the dictionary it is prime, so we yield it and record <code>n*n</code> as its first future composite; when <code>n</code> is present it is composite, so we advance that prime's marker by <code>2*p</code> to the next unoccupied slot. The accumulation loop then multiplies primes into <code>result</code> and, unlike the C version, *commits then checks*: it multiplies first, detects an overshoot, and divides the last prime back out before breaking. Both styles reach the answer in a handful of iterations.
</p>
</article>