notes.html

problem 48 · 24 lines

<article>
<h3>Problem Analysis</h3>
<p>
The task is to find the last ten decimal digits of the self-power sum 1<sup>1</sup> + 2<sup>2</sup> + ... + 1000<sup>1000</sup>. The pivotal observation is that "the last ten digits" of an integer is precisely that integer reduced <a class="reference-source" href="https://en.wikipedia.org/wiki/Modular_arithmetic" rel="noopener noreferrer" target="_blank">modulo</a> 10<sup>10</sup>. <a class="reference-source" href="https://en.wikipedia.org/wiki/Modular_arithmetic" rel="noopener noreferrer" target="_blank">Modular arithmetic</a> is the arithmetic of remainders: rather than tracking a full value, I track only its remainder after division by a fixed modulus m. The crucial property is that the modulus distributes over both addition and multiplication, so (a + b) mod m = ((a mod m) + (b mod m)) mod m, and the same holds for products. This means I never need the true sum at all - the largest term, 1000<sup>1000</sup>, has roughly 3000 decimal digits - because I can keep every intermediate value below 10<sup>10</sup>.
</p>
<p>
The problem then reduces to computing i<sup>i</sup> mod 10<sup>10</sup> for each i from 1 to 1000. Multiplying i by itself i times would cost O(i) multiplications per term. The standard speedup is <a class="reference-source" href="https://en.wikipedia.org/wiki/Modular_exponentiation" rel="noopener noreferrer" target="_blank">modular exponentiation</a> via <a class="reference-source" href="https://en.wikipedia.org/wiki/Exponentiation_by_squaring" rel="noopener noreferrer" target="_blank">exponentiation by squaring</a>, which decomposes the exponent into its binary digits and computes the power in O(log i) multiplications by repeatedly squaring the base. Across all 1000 terms the total work is O(N log N) - effectively instantaneous - and every reduced value fits comfortably in a machine integer.
</p>
<h3>Solution Approach</h3>
<h4>Modular Exponentiation with a Reduced Running Sum</h4>
<p>
Both the Python and C files implement the same algorithm. I iterate i from 1 to the limit inclusive, compute the term i<sup>i</sup> mod 10<sup>10</sup> by fast <a class="reference-source" href="https://en.wikipedia.org/wiki/Modular_exponentiation" rel="noopener noreferrer" target="_blank">modular exponentiation</a>, add it to a running total, and reduce that total modulo 10<sup>10</sup> after every addition. The final running total is the answer.
</p>
<p>
In Python I rely on the built-in three-argument <code>pow(i, i, modulo)</code>. This is not the same as <code>pow(i, i) % modulo</code>; the three-argument form performs the <a class="reference-source" href="https://en.wikipedia.org/wiki/Modular_arithmetic" rel="noopener noreferrer" target="_blank">modular</a> reduction inside the squaring loop, so the full multi-thousand-digit power is never materialised. Python integers are arbitrary precision, so there is no overflow to consider, and the routine runs in optimised C under the hood.
</p>
<p>
In C I wrote <code>mod_pow</code> by hand as a classic binary <a class="reference-source" href="https://en.wikipedia.org/wiki/Exponentiation_by_squaring" rel="noopener noreferrer" target="_blank">exponentiation by squaring</a> loop: while the exponent is positive, I test its lowest bit with <code>exp &amp; 1</code> to decide whether to fold the current base into the result, then square the base and right-shift the exponent. The subtlety is overflow. With a modulus of 10<sup>10</sup>, two reduced operands can each approach 10<sup>10</sup>, so their product can reach about 10<sup>20</sup> - well beyond the roughly 9.2x10<sup>18</sup> ceiling of a signed 64-bit <code>long long</code>. I avoid this by casting one operand to <code>__int128</code> before each multiply, computing the product at 128-bit precision, and immediately reducing modulo <code>mod</code> back into 64-bit range. The 128-bit value is purely transient and never stored across iterations.
</p>
<p>
Both versions accept the limit as a runtime argument rather than hard-coding 1000, so the same binary or script handles the small development case (limit 10, answer 405071317) and the full case (limit 1000, answer 9110846700) through the identical code path.
</p>
</article>