Detailed mathematical approach

Problem Summary

The task is to find the last ten decimal digits of

$1^1+2^2+3^3+\cdots+1000^{1000}.$

If we write

$S_n=\sum_{k=1}^{n} k^k,$

then the required quantity is simply \(S_{1000}\bmod 10^{10}\). The important point is that the problem is about the final ten-digit suffix, not about the full decimal expansion of the self powers themselves.

Mathematical Approach

Set \(M=10^{10}\). The entire computation can be organized around the modular prefix sum

$T_n\equiv \sum_{k=1}^{n} k^k \pmod M,$

which satisfies the simple recurrence

$T_n\equiv T_{n-1}+n^n \pmod M,\qquad T_0=0.$

So the real work is evaluating each self-power \(n^n\) modulo \(M\) quickly and safely.

Reduce the series immediately modulo \(10^{10}\)

Modular arithmetic respects both addition and multiplication:

$ (a+b)\bmod M = \bigl((a\bmod M)+(b\bmod M)\bigr)\bmod M,$

$ (ab)\bmod M = \bigl((a\bmod M)(b\bmod M)\bigr)\bmod M.$

Because of these identities, every term can be reduced as soon as it is formed, and the running sum can also be reduced after every addition. There is never any need to materialize the full number \(1000^{1000}\), whose decimal expansion is far larger than ten digits.

Compute one self-power with binary exponentiation

A direct computation of \(k^k\) would use \(k-1\) multiplications. The implementations instead use repeated squaring, which processes the binary expansion of the exponent \(k\). Starting from an accumulator equal to 1, they repeatedly square the current base, and whenever the current bit of the exponent is 1 they multiply that base into the accumulator.

The loop invariant is

$\text{accumulator}\cdot \text{base}^{e}\equiv k^k \pmod M,$

where \(e\) denotes the still-unprocessed part of the exponent. Each iteration preserves the invariant while cutting \(e\) roughly in half. When \(e=0\), the accumulator is exactly \(k^k\bmod M\).

This changes the cost of one term from \(O(k)\) multiplications to \(O(\log k)\) modular multiplications.

Worked example: the checkpoint at \(n=10\)

The implementations verify themselves on the smaller sum

$S_{10}=1^1+2^2+\cdots+10^{10}=10405071317.$

Therefore

$T_{10}\equiv 10405071317 \equiv 405071317 \pmod{10^{10}}.$

As a ten-digit suffix this is \(0405071317\). This example is useful because the unreduced sum already has more than ten digits, yet the modular method keeps only the information the problem actually asks for.

Why overflow still matters

Even after reduction, each stored residue is below \(10^{10}\), so a product of two residues can be almost \(10^{20}\). That exceeds ordinary 64-bit multiplication. The mathematics is unchanged, but the implementations need different arithmetic strategies: the C++ version widens the intermediate product to 128 bits, the Java version performs the modular products with arbitrary-precision integers, and the Python version relies on built-in big integers.

How the Code Works

Evaluate one term at a time

The C++, Python, and Java implementations iterate through \(k=1,2,\dots,n\). For each \(k\), they compute \(k^k\bmod 10^{10}\) with binary exponentiation: initialize the residue as 1, reduce the base modulo \(10^{10}\), square the base every round, multiply it into the residue when the current exponent bit is odd, and then shift the exponent to the right.

Accumulate the modular prefix sum

After one modular self-power is obtained, it is added to the running total and the sum is reduced modulo \(10^{10}\) immediately. This implements the recurrence \(T_n\equiv T_{n-1}+n^n\pmod{10^{10}}\) directly. The programs also include the checkpoint \(T_{10}=405071317\), which confirms that both the exponentiation routine and the summation logic behave correctly before the full case \(n=1000\) is evaluated.

Complexity Analysis

Computing \(k^k\bmod M\) costs \(O(\log k)\) modular multiplications, so the whole algorithm for \(n\) terms runs in

$O\!\left(\sum_{k=1}^{n}\log k\right)=O(n\log n).$

For \(n=1000\), this is very small. The memory usage is \(O(1)\), because only a handful of integers are stored: the current base, the current exponent, one accumulator, and the running total.

Footnotes and References

1. Project Euler 48 - Self powers
2. Wikipedia - Modular arithmetic
3. Wikipedia - Modular exponentiation
4. Wikipedia - Exponentiation by squaring