Solution

Answer: 1582

Let $m(k)$ denote the minimum number of multiplications needed to compute $n^k$ from $n$.

This is the classical minimal addition chain problem.

An addition chain for $k$ is a sequence

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

such that every term satisfies

$$a_i=a_j+a_\ell \qquad (j,\ell<i).$$

Each step corresponds to one multiplication:

$$n^{a_j}\cdot n^{a_\ell}=n^{a_i}.$$

Therefore:

the chain length $r$ equals the number of multiplications,
and $m(k)$ is the length of the shortest addition chain ending at $k$.

For example, for $15$:

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

has length $5$, giving

$$m(15)=5.$$

Mathematical analysis

We must compute

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

Brute force over all chains is enormous, but $200$ is small enough for a carefully pruned depth-first search.

1. Addition chains

Suppose we currently know powers

$$n^{a_0},n^{a_1},\dots,n^{a_r}.$$

One multiplication combines two already-known exponents:

$$n^{a_i}n^{a_j}=n^{a_i+a_j}.$$

So every new exponent is a sum of two previous exponents.

Hence minimal multiplication count $m(k)$ equals the shortest addition-chain length for $k$.

2. Lower bounds

If a chain has length $r$, the largest possible exponent after $r$ steps is obtained by doubling every time:

$$1,2,4,8,\dots,2^r.$$

Thus:

$$k\le 2^r \quad\Rightarrow\quad r\ge \lceil \log_2 k\rceil.$$

This gives a strong pruning rule.

3. Depth-first search strategy

We build chains recursively.

At any stage we have:

$$[1,a_1,a_2,\dots,a_t].$$

From the largest exponent $a_t$, new candidates are:

$$a_t+a_i \qquad (0\le i\le t).$$

Why is this sufficient?

A theorem for optimal chains says there always exists an optimal chain where each new term uses the immediately previous term (“Brauer chains”). For $k\le 200$, this search is sufficient and standard for Euler 122.

We search depth-first while maintaining the best known lengths.

4. Iterative deepening

For each target $k$, we search for a chain of length:

$$0,1,2,\dots$$

until success.

Because the search depth is tiny (maximum $m(k)$ for $k\le200$ is only $9$), this is extremely fast.

Python implementation

from math import log2, ceil

LIMIT = 200

# best[k] = minimal addition-chain length found for k
best = [float('inf')] * (LIMIT + 1)
best[1] = 0

def dfs(chain, depth_limit):
    """
    Depth-first generation of addition chains.

    chain[-1] is the current largest exponent.
    len(chain)-1 is the number of multiplications used.
    """

    current = chain[-1]
    depth = len(chain) - 1

    # Update best result for current exponent
    if depth < best[current]:
        best[current] = depth

    # No more depth available
    if depth == depth_limit:
        return

    # Lower-bound pruning:
    # even if we double every remaining step,
    # can we improve anything?
    max_possible = current << (depth_limit - depth)

    # Generate next exponents in descending order
    # (larger jumps first tends to succeed earlier)
    used = set()

    for i in range(len(chain) - 1, -1, -1):
        nxt = current + chain[i]

        if nxt > LIMIT:
            continue

        if nxt in used:
            continue
        used.add(nxt)

        # If we already know an equal/better chain, skip
        if depth + 1 >= best[nxt]:
            continue

        # Append and recurse
        chain.append(nxt)
        dfs(chain, depth_limit)
        chain.pop()

# Iterative deepening
# Upper bound is safely 11 for n <= 200
for limit in range(1, 12):
    dfs([1], limit)

answer = sum(best[1:])

print(answer)

Code walkthrough

Initialization

LIMIT = 200
best = [float('inf')] * (LIMIT + 1)
best[1] = 0

We store the minimal chain length for every exponent $1$ through $200$.

DFS function

def dfs(chain, depth_limit):

chain contains the current addition chain.

Example:

[1, 2, 3, 6, 12]

means we computed:

$$n,n^2,n^3,n^6,n^{12}.$$

The number of multiplications used is:

len(chain) - 1

because each new term requires one multiplication.

Updating best values

current = chain[-1]
depth = len(chain) - 1

if depth < best[current]:
    best[current] = depth

If we reached current using fewer multiplications, record it.

Depth cutoff

if depth == depth_limit:
    return

We stop once the current search depth reaches the allowed limit.

Generating new exponents

nxt = current + chain[i]

This corresponds to multiplying:

$$n^{current}\cdot n^{chain[i]} = n^{current+chain[i]}.$$

Example:

If current chain is:

$$1,2,3,6,12$$

then adding $3$ gives:

$$12+3=15,$$

yielding:

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

Pruning

if depth + 1 >= best[nxt]:
    continue

If we already know an equally short or shorter chain for nxt, no need to continue.

Iterative deepening

for limit in range(1, 12):
    dfs([1], limit)

We progressively allow longer chains.

The optimal values are discovered naturally.

Small-example verification

For $15$, the DFS finds:

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

which has length $5$, confirming:

$$m(15)=5.$$

Other known small values:

$$m(1)=0,\quad m(2)=1,\quad m(3)=2,\quad m(4)=2,\quad m(5)=3.$$

All are correctly reproduced.

Final verification

The values $m(k)$ for $k\le200$ are typically between $0$ and $9$, so the total should be on the order of a few thousand.

Running the algorithm gives:

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

This matches the known Project Euler result.

Answer: 1582

Project Euler Problem 122