notes.html
problem 75 · 21 lines
<article>
<h3>Problem Analysis</h3>
<p>
The structure that makes this problem tractable is the arithmetic of <a class="reference-source" href="https://en.wikipedia.org/wiki/Pythagorean_triple" rel="noopener noreferrer" target="_blank">Pythagorean triples</a> - integer triples (a, b, c) with a^2 + b^2 = c^2, which describe the side lengths of right-angled triangles. A triple is <em>primitive</em> when gcd(a, b, c) = 1, meaning the sides share no common factor; every other triple is an integer multiple of a primitive one. <a class="reference-source" href="https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple" rel="noopener noreferrer" target="_blank">Euclid's formula</a> states that every primitive triple is generated uniquely by a pair (m, n) with m > n > 0, gcd(m, n) = 1, and m, n of opposite parity (one odd, one even), via a = m^2 - n^2, b = 2mn, c = m^2 + n^2. This is the key that converts a hopeless two-dimensional search over (a, b, c) - which would be O(L^2) - into a one-dimensional enumeration over generator pairs.
</p>
<p>
What I actually care about is the perimeter L = a + b + c. For a primitive triple this collapses beautifully: L = (m^2 - n^2) + 2mn + (m^2 + n^2) = 2m^2 + 2mn = 2m(m + n). The k-th multiple of that primitive triple has perimeter exactly k * 2m(m + n). Because the smallest perimeter for a fixed m occurs at n = 1, giving 2m(m + 1) > 2m^2, the generator m is bounded by sqrt(L / 2) - a tight, analytically derived limit. The algorithm is then a <a class="reference-source" href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noopener noreferrer" target="_blank">sieve</a>: for each primitive perimeter p, mark every multiple k * p <= L, counting how many triples land on each perimeter, then tally the perimeters hit exactly once. Summing L/p over all primitive perimeters follows the <a class="reference-source" href="https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)" rel="noopener noreferrer" target="_blank">harmonic series</a>, placing the total work at roughly O(L log L) - the same class as a prime sieve.
</p>
<h3>Solution Approach</h3>
<h4>Sieve over primitive perimeters (C and Python)</h4>
<p>
Both files implement the same algorithm; they differ only in language and the data structure used to accumulate counts. I enumerate generator pairs (m, n) with m > n, gcd(m, n) = 1, and opposite parity. For each valid pair I compute the primitive perimeter p = 2 * m * (m + n), then walk k = 1, 2, 3, ... incrementing a counter for k * p as long as it stays within the limit. After enumeration I count how many perimeter values were hit exactly once - that is the answer.
</p>
<p>
The outer loop runs m from 2 up to sqrt(max_perimeter / 2). The inner loop over n begins at <code>m % 2 + 1</code> and steps by 2: this guarantees m - n is odd, so m and n always have opposite parity, with no per-iteration parity test. The <a class="reference-source" href="https://en.wikipedia.org/wiki/Euclidean_algorithm" rel="noopener noreferrer" target="_blank">gcd</a> check then removes the remaining non-primitive generators. Together these two conditions ensure each primitive triple is generated exactly once, so no perimeter is ever double-counted by accident.
</p>
<p>
The languages diverge only in storage. In C I allocate a flat <code>int</code> array of size max_perimeter + 1 with <code>calloc</code>, indexing directly by perimeter value - O(1) writes and a cache-friendly final linear scan. I guard the multiple loop against overflow by widening <code>k * p</code> to <code>long long</code> before comparing. In Python I use a <a class="reference-source" href="https://docs.python.org/3/glossary.html#term-generator" rel="noopener noreferrer" target="_blank">generator function</a> that yields perimeters one at a time and a <a class="reference-source" href="https://docs.python.org/3/library/stdtypes.html#dict" rel="noopener noreferrer" target="_blank">dictionary</a> to accumulate counts. The benchmark shows the consequence of these language choices: on the main case (L = 1,500,000) C runs in 0.0083 s against Python's 0.3477 s, roughly a 40x gap typical of tight integer loops.
</p>
</article>