notes.html
problem 12 · 12 lines
<article>
<h3>Problem Analysis</h3>
<p>The n-th <a class="reference-source" href="https://en.wikipedia.org/wiki/Triangular_number" rel="noopener noreferrer" target="_blank">triangular number</a> is T(n) = n(n+1)/2, the sum of the first n natural numbers. We want the first such number with more than 500 divisors. The key tool is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Divisor_function" rel="noopener noreferrer" target="_blank">divisor-counting function</a> d(m): if m has the <a class="reference-source" href="https://en.wikipedia.org/wiki/Integer_factorization" rel="noopener noreferrer" target="_blank">prime factorization</a> m = p1^a1 * p2^a2 * ... * pk^ak, then d(m) = (a1+1)(a2+1)...(ak+1). The reasoning is combinatorial: every divisor is built by choosing, independently, an exponent from 0 to ai for each prime, so the product of the (ai+1) choice-counts gives the total number of divisors. This is far cheaper than enumerating divisors directly.</p>
<p>To factor an individual number we use <a class="reference-source" href="https://en.wikipedia.org/wiki/Trial_division" rel="noopener noreferrer" target="_blank">trial division</a> up to the square root: any composite m has a factor no larger than sqrt(m), so testing divisors d while d*d <= m suffices, with any residue greater than 1 being a prime that occurs once. This costs O(sqrt(m)) per number. The structural observation that makes the search fast is that n and n+1 are <a class="reference-source" href="https://en.wikipedia.org/wiki/Coprime_integers" rel="noopener noreferrer" target="_blank">coprime</a> (consecutive integers share no common factor), and the divisor function is <a class="reference-source" href="https://en.wikipedia.org/wiki/Multiplicative_function" rel="noopener noreferrer" target="_blank">multiplicative</a>: d(a*b) = d(a)*d(b) when gcd(a,b)=1. Since exactly one of n, n+1 is even, T(n) splits into two coprime halves, and we can count divisors on numbers roughly half the magnitude of T(n) itself.</p>
<h3>Solution Approach</h3>
<h4>Algorithm 0: Multiplicative split into coprime halves (p0012_s0.py, p0012_s0_c)</h4>
<p>This approach exploits multiplicativity directly. At each step I look at the parity of <code>i</code>. If <code>i</code> is even, T(i) = (i/2)*(i+1); if <code>i</code> is odd, T(i) = i*((i+1)/2). In both cases the two factors are coprime, so <code>d(T(i)) = num_factors(first) * num_factors(second)</code>. The dividing-by-two folds the /2 of the triangular formula into whichever factor is even, keeping both operands exact integers and roughly half the size of T(i). The loop advances <code>i</code> and recomputes <code>triangle_number = i*(i+1)/2</code> at the bottom, so the value returned when the divisor count first exceeds the target is correct. Factoring two smaller numbers instead of one large one is the entire payoff: trial division cost scales with the square root, so two halves are cheaper than the whole.</p>
<p>The Python and C versions are logically identical. C uses <code>long long</code> for the triangle number as a defensive choice against overflow, and folds the leftover-prime case into <code>result *= 2</code> (an unconsumed residue is a prime with exponent 1, contributing a factor of 2). Python's <code>prime_factorization</code> returns explicit (prime, exponent) tuples, which <code>num_factors</code> then reduces to the product of (exp+1).</p>
<h4>Algorithm 1: Direct trial division per triangular number (p0012_s1.py, p0012_s1_c)</h4>
<p>This is the straightforward baseline. For each T(i) I factor the whole number by trial division and compute d(T(i)) from the exponents, advancing through triangular numbers until the count exceeds the target. There is no coprime split; each triangular number is treated as an independent factorization problem. The code is simpler - the loop condition is just <code>num_factors(triangle_number) < num_divisors</code> - but it factors a number twice as large as either half in Algorithm 0, doing more work per step.</p>
</article>