Detailed mathematical approach

Problem Summary

For each integer \(k\) with \(1 \le k \le 200\), let \(m(k)\) be the smallest number of multiplications needed to build \(a^k\) starting from \(a\), when every new power must be obtained by multiplying two powers that are already available. The problem asks for the total

$\sum_{k=1}^{200} m(k).$

If we track exponents instead of powers, each multiplication turns known exponents \(x\) and \(y\) into the new exponent \(x+y\). The question is therefore an addition-chain problem: how short can a chain ending at \(k\) be?

Mathematical Approach

An addition chain for \(k\) is a sequence

$1=a_0<a_1<\cdots<a_r=k,$

where every later term is obtained from earlier ones by

$a_t=a_i+a_j \qquad (0 \le i,j < t).$

The length \(r\) is exactly the number of multiplications, so \(m(k)\) is the minimum possible length.

The State Space That Is Actually Searched

The implementations restrict the search to star chains, also called Brauer chains, where each new exponent must use the current largest exponent:

$a_{t+1}=a_t+a_i \qquad (0 \le i \le t).$

This models the move “take the newest available power and multiply it by one earlier power”. Because all chain elements are positive, every new term is larger than the previous one, so the chain stays strictly increasing automatically.

For the range required here, that restricted search space is enough: every exponent \(k \le 200\) attains its true minimum inside the star-chain search, so filling the table for all \(k\) gives the values demanded by the problem.

Why Iterative Deepening Produces Optimal Lengths

Fix a depth limit \(d\). A depth-limited DFS can enumerate every star chain of length at most \(d\). If some target \(k\) appears during that sweep, then \(k\) has a chain of length \(d\) or less.

The search is repeated for

$d=1,2,3,\dots,$

so the first depth at which \(k\) becomes reachable is its minimal length inside the searched family of chains. The code does not solve one target at a time; instead, one global pass keeps improving a table of best-known lengths for all intermediate exponents that appear anywhere in the search tree.

The Key Pruning Invariant

Suppose the current chain reaches an exponent \(n\) at depth \(d\). If the table already contains a shorter route to \(n\), then exploring from this occurrence cannot improve \(m(n)\). That is why the search prunes whenever

$d > \text{best}(n).$

This bound is monotone: once a value is stored in the best table, it can only stay the same or decrease. Every recursive call therefore uses the strongest information found so far.

Notice that branches with \(d=\text{best}(n)\) are still explored. Two different chains can reach the same exponent with the same length, but their later extensions can differ. Keeping equal-depth alternatives matters because one such branch may lead to a shorter chain for a larger target.

Worked Example: \(m(15)=5\)

A concrete chain for \(15\) is

$1,2,3,6,12,15.$

Interpreted as powers, this means

$a^2=a\cdot a,\quad a^3=a^2\cdot a,\quad a^6=a^3\cdot a^3,\quad a^{12}=a^6\cdot a^6,\quad a^{15}=a^{12}\cdot a^3.$

So \(m(15)\le 5\). The depth-by-depth search proves optimality: the full depth-4 sweep finds no chain ending at \(15\), while the depth-5 sweep does. Therefore

$m(15)=5.$

This same argument is applied simultaneously to every \(k \le 200\), and the final result is the sum of all these minimal lengths.

How the Code Works

The C++, Python, and Java implementations create an array of best-known multiplication counts for the exponents \(1\) through \(200\). The entry for \(1\) is initialized to \(0\), while all other entries start as “unknown”. The current chain starts as the one-term chain \([1]\).

Next comes iterative deepening. For each allowed depth, the implementation performs a DFS that takes the last exponent in the current chain and combines it with each earlier exponent, from larger addends to smaller ones. Every candidate

$n=a_t+a_i$

is ignored if \(n>200\). Otherwise, the table is updated when the new chain is shorter than the best one known so far for \(n\).

After recording a candidate, the DFS recurses on the extended chain and then removes that last term again on the way back up the recursion. In this way the search explores the whole tree of possibilities while storing only the current path. After each depth sweep, the code checks whether every exponent up to \(200\) now has a finite value. As soon as that is true, the search stops and the program adds the table entries.

All three language versions implement the same mathematical idea: iterative deepening over star chains, a global best-depth table for pruning, and a final summation over the completed table.

Complexity Analysis

Exact addition-chain search is exponential in the maximum depth being explored. At depth \(t\), there are at most \(t+1\) choices for the addend paired with the current largest exponent, so the raw search tree grows very quickly as the allowed depth increases.

For this Project Euler instance the constants are small. The target range ends at \(200\), the search stops as soon as every value has been reached, and the best-known table removes many branches that cannot improve anything. Memory usage is modest: \(O(200)\) for the best table plus \(O(D)\) for the current chain and recursion stack, where \(D\) is the deepest chain length actually explored.

Footnotes and References

1. Problem page: Project Euler 122 - Efficient exponentiation
2. Addition chains: Wikipedia - Addition chain
3. Star chains and related terminology: MathWorld - Addition Chain
4. Iterative deepening depth-first search: Wikipedia - IDDFS
5. Repeated squaring as a standard comparison point: Wikipedia - Exponentiation by squaring