notes.html

problem 21 · 11 lines

<article>
<h3>Problem Analysis</h3>
<p>This problem revolves around the <a class="reference-source" href="https://en.wikipedia.org/wiki/Divisor_function" rel="noopener noreferrer" target="_blank">divisor function</a>, specifically the sum of <a class="reference-source" href="https://en.wikipedia.org/wiki/Divisor#Further_notions_and_facts" rel="noopener noreferrer" target="_blank">proper divisors</a> of a number n - the positive integers strictly less than n that divide n evenly. We call this d(n). Two distinct numbers a and b form an <a class="reference-source" href="https://en.wikipedia.org/wiki/Amicable_numbers" rel="noopener noreferrer" target="_blank">amicable pair</a> when d(a) = b and d(b) = a. The task is to sum every number under 10,000 that participates in such a pair. The crucial observation is that we do not need to search for pairs directly: for each candidate x we compute y = d(x), then check whether d(y) = x and y differs from x. If so, x is <a class="reference-source" href="https://en.wikipedia.org/wiki/Amicable_numbers" rel="noopener noreferrer" target="_blank">amicable</a>. The condition y != x is what excludes <a class="reference-source" href="https://en.wikipedia.org/wiki/Perfect_number" rel="noopener noreferrer" target="_blank">perfect numbers</a>, where d(n) = n - these are not <a class="reference-source" href="https://en.wikipedia.org/wiki/Amicable_numbers" rel="noopener noreferrer" target="_blank">amicable</a> because the definition demands two distinct numbers.</p>
<p>The efficiency hinges on how we compute d(n). A naive approach tests every integer from 1 to n-1, costing O(n) per number. Instead I enumerate divisors in pairs: every divisor i below the square root of n has a matching co-divisor n/i above it. By iterating only from 2 to floor(sqrt(n)) and harvesting both i and n/i whenever i divides n, the cost per number drops to O(sqrt(n)). The single subtlety is a perfect square, where sqrt(n) pairs with itself and would be counted twice - so I subtract it once. Across all numbers up to a limit N, the total work is O(N * sqrt(N)), which for N = 10,000 is roughly one million operations - trivial for a modern machine.</p>
<h3>Solution Approach</h3>
<h4>Trial Division with Divisor Pairing (Python and C)</h4>
<p>The Python solution (<code>p0021_s0.py</code>) and the C solution (<code>p0021_s0.c</code>) implement the same algorithm in two languages. The heart of both is <code>sum_factors(n)</code>, which computes d(n). I initialise the running total to 1, since 1 is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Divisor#Further_notions_and_facts" rel="noopener noreferrer" target="_blank">proper divisor</a> of every n greater than 1. I then loop i from 2 up to <code>n_sqrt = floor(sqrt(n))</code>; whenever <code>n % i == 0</code>, I add both i and n/i to the total. Finally, if <code>n_sqrt * n_sqrt == n</code>, the number is a perfect square and its square root was added twice (once as i, once as n/i), so I subtract it once. This formulation is correct by construction and avoids any conditional inside the hot loop other than the divisibility test.</p>
<p>The main loop walks x from 2 to <code>max_num</code> inclusive. For each x, it evaluates <code>y = sum_factors(x)</code>, then accepts x as <a class="reference-source" href="https://en.wikipedia.org/wiki/Amicable_numbers" rel="noopener noreferrer" target="_blank">amicable</a> when both <code>y != x</code> and <code>sum_factors(y) == x</code>. I deliberately placed the inexpensive comparison <code>y != x</code> first so that the more expensive second divisor-sum call is short-circuited whenever x is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Perfect_number" rel="noopener noreferrer" target="_blank">perfect number</a> or self-mapping. I do not constrain y to lie within <code>max_num</code>, because an <a class="reference-source" href="https://en.wikipedia.org/wiki/Amicable_numbers" rel="noopener noreferrer" target="_blank">amicable</a> partner can legitimately fall outside the search window while the number itself is inside it - the membership condition is on x, not on its partner.</p>
<p>The Python version memoises <code>sum_factors</code> with <a class="reference-source" href="https://docs.python.org/3/library/functools.html#functools.lru_cache" rel="noopener noreferrer" target="_blank">functools.lru_cache</a>, but defines the helper inside <code>solve()</code> rather than at module scope, so the cache is rebuilt on every call. This is a deliberate benchmarking choice: the harness invokes <code>solve()</code> many times in one process to average its runtime, and a module-level cache would survive between those runs - the first run would pay the full cost and every later run would read cached answers, reporting a falsely low time. A per-call cache is discarded and rebuilt each run, so the recorded average reflects the true cost of one solve. The C version omits <a class="reference-source" href="https://en.wikipedia.org/wiki/Memoization" rel="noopener noreferrer" target="_blank">memoisation</a> entirely because C offers no built-in equivalent and the problem is small enough that recomputation is cheap. The benchmark bears this out: C runs in about 1.6 ms while Python takes about 22 ms, a roughly 14x gap driven mainly by interpreter overhead rather than the caching difference.</p>
</article>