Detailed mathematical approach

Problem Summary

We consider all natural numbers \(a,b\) with \(1 \le a,b < 100\) and ask for the largest possible decimal digit sum of \(a^b\). If we write the digit-sum function as \(s(n)\), the goal is to maximize \(s(a^b)\) over the \(99 \times 99 = 9801\) candidate pairs.

The search space in \((a,b)\) is small, but the values themselves are not. The largest candidate, \(99^{99}\), already has almost 200 decimal digits, so fixed-width arithmetic is not enough. The right approach is therefore not deeper number theory, but exact decimal arithmetic with reuse from one exponent to the next.

Mathematical Approach

The implementations all exploit the same idea: for a fixed base \(a\), compute the powers \(a^1,a^2,\dots,a^{99}\) incrementally. Instead of rebuilding each power from scratch, store the current power in base 10 and multiply that representation by \(a\) once per step.

How large can the candidates become?

For any \(a > 1\), the number of decimal digits of \(a^b\) is

$d(a,b)=\lfloor b\log_{10} a \rfloor+1.$

This gives an immediate size bound for the whole problem. Since

$d(99,99)=\lfloor 99\log_{10}99 \rfloor+1=198,$

every candidate fits into a decimal array of length at most 198. That is far too large for ordinary machine integers, but tiny for a manual big-integer representation.

Represent each power as a decimal vector

For a fixed base \(a\), write the current power \(a^b\) as

$a^b=\sum_{i=0}^{m_b-1} d_i^{(b)}10^i,\qquad 0 \le d_i^{(b)} \le 9.$

The digits are stored from least significant to most significant, so the coefficient list is exactly the decimal expansion in little-endian order. With this notation, the quantity we want to maximize is simply

$s(a^b)=\sum_{i=0}^{m_b-1} d_i^{(b)}.$

Once the decimal digits are available, the digit sum is just a linear scan of the vector.

The carry recurrence for \(a^b \to a^{b+1}\)

Suppose the digits of \(a^b\) are already known. To obtain \(a^{b+1}=a \cdot a^b\), multiply the digit vector by the small integer \(a\) exactly as in schoolbook arithmetic. Start with carry \(c_0=0\), and for each position \(i\) define

$t_i=a\,d_i^{(b)}+c_i,$

$d_i^{(b+1)}=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$

After the old digits are exhausted, any remaining carry is split into decimal digits and appended to the vector. This recurrence is the core mathematical object behind all three implementations.

The invariant that makes the update correct

After processing positions \(0,1,\dots,i-1\), the multiplication step maintains the identity

$a\sum_{j=0}^{i-1} d_j^{(b)}10^j=\sum_{j=0}^{i-1} d_j^{(b+1)}10^j+c_i10^i.$

So the lower \(i\) digits of the new power are already correct, and every unprocessed contribution has been compressed into the single carry term \(c_i10^i\). When the scan ends and the final carry is flushed, the whole product \(a^{b+1}\) has been reconstructed exactly.

Worked example: building \(99^2\) from \(99\)

Start with \(99^1=99\), stored as digits \([9,9]\).

At the units digit,

$9 \cdot 99 + 0 = 891,$

so we write \(1\) and carry \(89\).

At the tens digit,

$9 \cdot 99 + 89 = 980,$

so we write \(0\) and carry \(98\).

Now the original digit vector is finished, and the remaining carry \(98\) contributes the last two digits \(8\) and \(9\). The new vector is \([1,0,8,9]\), which means

$99^2=9801,\qquad s(99^2)=9+8+0+1=18.$

One more application of the same recurrence gives \(99^3=970299\), again without restarting from scratch.

Why exhaustive search is already enough

Once decimal multiplication is available, the remaining search is tiny. There are only 9801 pairs \((a,b)\), and for each fixed base \(a\) the sequence of powers is generated in order by repeated multiplication. No pruning is required, and no candidate is missed: after the \(b\)-th multiplication, the maintained vector is exactly \(a^b\).

The cases \(a=1\) or \(b=1\) are harmless and can stay in the sweep. They never produce the optimum, but including them keeps the code uniform and the mathematics cleaner.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. For each base \(a\), they reset the current decimal vector to \([1]\), representing \(a^0=1\). Then they iterate the exponent from \(1\) up to the chosen limit, multiply the vector by \(a\), compute the digit sum of the updated vector, and compare it with the best value seen so far.

The multiplication step is performed directly on the stored decimal digits. Each digit is replaced by its new value modulo 10, while the quotient becomes the carry for the next position. If a carry remains after the last stored digit, new digits are appended until the carry vanishes. Because the digits are stored least-significant first, the carry naturally moves forward through the list.

The implementations therefore never need floating-point arithmetic, never recompute an already known power, and never store more than one current power per base. They also include a small checkpoint on the reduced range \(a,b \le 10\), where the correct maximum digit sum is \(45\), to confirm that the digit machinery is behaving correctly.

Complexity Analysis

Let \(A=99\), \(B=99\), and let

$D=\max_{1 \le a,b \le 99} d(a,b)=198.$

For one state \((a,b)\), the multiplication-by-\(a\) step touches each stored digit once, and the digit-sum pass also touches each stored digit once. So each state costs \(O(D)\) time, giving an overall running time of

$O(ABD).$

In this problem that means only a few million digit operations, which is why the full exhaustive search is easily practical. The memory usage is \(O(D)\), because the implementation stores only the current power's decimal digits plus a few scalar counters.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=56
2. Digit sum: Wikipedia - Digit sum
3. Positional notation: Wikipedia - Positional notation
4. Arbitrary-precision arithmetic: Wikipedia - Arbitrary-precision arithmetic
5. Multiplication algorithm: Wikipedia - Multiplication algorithm