notes.html
problem 72 · 65 lines
<article>
<h3>Problem Analysis</h3>
<p>
The problem asks me to count reduced proper fractions <code>n/d</code> with <code>1 <= n < d</code>
whose numerator and denominator share no common factor other than 1, for every denominator up to one
million. Two integers whose greatest common divisor is 1 are called <a class="reference-source" href="https://en.wikipedia.org/wiki/Coprime_integers" rel="noopener noreferrer" target="_blank">coprime</a>.
The decisive observation is that for a fixed denominator <code>d</code>, the number of valid numerators is
exactly the count of integers in <code>1..d-1</code> that are coprime to <code>d</code> - and that quantity
is precisely <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 <code>phi(d)</code>. So the answer to a question about coprime fractions collapses into a single
sum: the running total of <code>phi(d)</code> from <code>d = 2</code> up to the limit. I start at 2 rather
than 1 because <code>phi(1) = 1</code> would count <code>1/1</code>, which is not a proper fraction with
<code>n < d</code>.
</p>
<p>
The remaining work is computing <code>phi(d)</code> for every <code>d</code> efficiently. The totient is a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Multiplicative_function" rel="noopener noreferrer" target="_blank">multiplicative function</a>
given by <code>phi(d) = d * product over distinct primes p dividing d of (1 - 1/p)</code>. Because this is a
product over prime factors, I can compute all totients up to <code>N</code> simultaneously with a sieve
modelled on the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a>:
seed each <code>phi[d] = d</code>, then for every prime <code>p</code> apply the factor <code>(p-1)/p</code>
to each multiple of <code>p</code>. The cost is dominated by the inner loops, which run
<code>N/2 + N/3 + N/5 + ...</code> times over the primes - a sum that grows like
<code>N log log N</code>, the same near-linear bound as the <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">Sieve of Eratosthenes</a>
itself. Memory is <code>O(N)</code>. Both are entirely practical even at <code>N = 10^7</code>.
</p>
<h3>Solution Approach</h3>
<h4>Euler Totient Sieve (Python and C)</h4>
<p>
Both files implement the same <a class="reference-source" href="https://en.wikipedia.org/wiki/Euler%27s_totient_function" rel="noopener noreferrer" target="_blank">totient</a>
sieve; the C version exists purely for speed. The algorithm proceeds as follows:
</p>
<ul>
<li>
Allocate an array <code>euler_totients</code> of length <code>max_d + 1</code> and set
<code>euler_totients[d] = d</code>. This is the "no prime factors applied yet" identity value, matching
the leading <code>d</code> in the product formula. In Python I write this compactly as
<code>list(range(max_d + 1))</code>; in C it is a single initialisation loop.
</li>
<li>
Iterate <code>n</code> from 2 upward. If <code>euler_totients[n] == n</code>, no smaller prime has yet
touched this cell, so <code>n</code> must itself be prime. This doubles as the primality test - I need no
separate boolean sieve.
</li>
<li>
When <code>n</code> is prime, I walk every multiple <code>j = n, 2n, 3n, ...</code> and apply
<code>euler_totients[j] = euler_totients[j] / n * (n - 1)</code>. Each distinct prime factor of
<code>j</code> is applied exactly once this way, so once all primes <code><= j</code> have been
processed, the cell at <code>j</code> holds its true totient.
</li>
<li>
I accumulate <code>result += euler_totients[n]</code> in the same outer loop. This is correct because
every prime factor of <code>n</code> is at most <code>n</code>, so the totient of <code>n</code> is fully
finalised by the time the outer loop reaches index <code>n</code>.
</li>
</ul>
<p>
The two implementations differ only in their host language. The C version uses <code>malloc</code> for the
heap array and <code>long long</code> to hold the running total (about 3.0e11 at <code>max_d = 1000000</code>,
and roughly 3.0e13 at <code>10^7</code> - both comfortably inside a 64-bit integer). The Python version
relies on arbitrary-precision integers and a built-in list, so there is no overflow concern at all. Both run
one linear outer pass with nested per-prime inner passes.
</p>
</article>