Problem 122: Efficient Exponentiation

Project Euler Problem 122 Solution

EulerSolve provides an optimized solution for Project Euler Problem 122, Efficient Exponentiation, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

Problem Summary

Starting from a number $n$, we may multiply any two powers of $n$ that we already have, or a power by itself. Let $m(k)$ be the smallest number of multiplications that produces $n^k$, so that $m(1)=0$. The statement computes $n^{15}$ with $14$ multiplications naively, with $6$ by a “binary” method and with only $5$ by way of $n^2$, $n^3$, $n^6$ and $n^{12}$; indeed $m(15)=5$. We must find $\sum_{k=1}^{200}m(k)$. ^[1]

The whole solution in one sentence: writing down only the exponents turns every multiplication into an addition, so $m(k)$ is the length of a shortest addition chain for $k$, and all $200$ lengths come from one search that lengthens chains a step at a time, always adds an earlier number to the newest one and drops every chain that reaches a number later than necessary.

Mathematical Approach

Sections 1 to 4 translate the problem and show why simple rules fail; Sections 5 to 8 describe the program's search, prove that it finds $m(k)$ for every $k\le200$ and run it by hand.

1. From multiplications to addition chains

Since $n^x\cdot n^y=n^{x+y}$, each multiplication adds two exponents that we already have. An addition chain for $k$ is a sequence

$$1=a_0\lt a_1\lt a_2\lt\cdots\lt a_r=k$$

in which every term after the first is the sum of two earlier terms, $a_t=a_i+a_j$ with $i,j\lt t$, where $i=j$ is allowed. Its length $r$ is the number of these additions. ^[2] The five multiplications of the statement give the chain $1,2,3,6,12,15$, and its binary method gives $1,2,4,8,12,14,15$.

Claim: $m(k)$ is the smallest length of an addition chain for $k$. ^[3] A chain of length $r$ is a plan with $r$ multiplications: compute $n^{a_t}=n^{a_i}\cdot n^{a_j}$ for $t=1,\dots,r$. Conversely, take a plan that reaches $n^k$ with $s$ multiplications and list $1$ and the exponents it produces. Since $x+y$ is larger than both $x$ and $y$, an exponent above $k$ only leads to exponents above $k$; drop these, drop repetitions and sort the rest. Each remaining exponent other than $1$ is the sum of two smaller ones produced before it, which are also in the list, so the list is an addition chain for $k$ of length at most $s$. Since a chain increases, none of its terms exceeds $k$, and a search for all $k\le200$ never needs numbers above $200$.

2. Small values by hand

The chains of length at most $2$ are $1$; $1,2$; $1,2,3$ and $1,2,4$. After $1,2,3$ the next term can be $4$, $5$ or $6$, and after $1,2,4$ it can be $5$, $6$ or $8$, so there are exactly six chains of length $3$, and they end at $4$, $5$, $6$ and $8$. Hence $7$, $9$ and $10$ need four steps, and four are enough: $1,2,3,5,7$, $1,2,4,8,9$ and $1,2,4,8,10$. This gives

$$\begin{aligned}m(1),\dots,m(5)&=0,1,2,2,3,\\m(6),\dots,m(10)&=3,4,3,4,4,\end{aligned}$$

with the sum $26$, which the C++ program checks before it starts.

3. Two easy bounds

Every step at most doubles the largest number: $a_t=a_i+a_j\le2a_{t-1}$, so by induction $a_t\le2^t$, with equality only if all steps so far were doublings. Hence

$$m(k)\ge\lceil\log_2k\rceil.$$

An upper bound comes from the binary method. Let $\lambda(k)=\lfloor\log_2k\rfloor$, and let $\nu(k)$ be the number of digits $1$ of $k$ in base $2$. Squaring $\lambda(k)$ times gives $n^{2^i}$ for every $2^i\le k$, and multiplying together the $\nu(k)$ of these powers that belong to the digits $1$ of $k$ takes $\nu(k)-1$ more multiplications. So

$$m(k)\le\lambda(k)+\nu(k)-1.$$

For $15=1111_2$ this gives $3+3=6$, the binary method of the statement. ^[4] A second rule is the factor method: if $k=ab$, a chain for $a$ followed by the terms after the first of a chain for $b$, each multiplied by $a$, is a chain for $k$, so $m(ab)\le m(a)+m(b)$. ^[2] For $15=3\cdot5$, the chain $1,2,3$ followed by $3\cdot(2,4,5)=6,12,15$ is exactly the five-step plan of the statement.

4. Why a search is needed

To prove $m(15)=5$ we must rule out four steps. In a chain of length $4$ for $15$, the last step gives $15\le2a_3$, so $a_3\ge8$; together with $a_3\le2^3$ this forces $a_3=8$ and therefore the doubling chain $1,2,4,8$. But no sum of two of the numbers $1,2,4,8$ equals $15$. So $m(15)=5$, while the binary method needs $6$; $15$ is the smallest exponent for which that method is not optimal. ^[4] The factor method fails as well: for $33=3\cdot11$ it gives $m(3)+m(11)=2+5=7$, but $1,2,4,8,16,32,33$ has length $6$, which is optimal by Section 3. No efficient algorithm for shortest chains is known, and the variant in which a chain must contain several given numbers is NP-complete. ^[2] So we search.

5. Star chains

In a star chain, also called a Brauer chain, every new term uses the newest one: $a_{t+1}=a_t+a_i$ for some $i\le t$. ^[2] ^[5] All chains shown so far are star chains; in $1,2,3,6,12,15$, for instance, $15=12+3$. Star chains are easy to enumerate: after $a_t$ there are exactly $t+1$ choices of $a_i$, and they give $t+1$ different numbers, all larger than $a_t$. So there are exactly $1\cdot2\cdots r=r!$ star chains of length $r$, for example $11!=39\,916\,800$ of length $11$.

Restricting the search to star chains can lose shortest chains, but not below $12509$: Hansen showed that some numbers have no shortest star chain, and $12509$ is the smallest of them. ^[2]

6. Tight chains and the pruning test

The program keeps a table of the fewest steps in which it has reached each $x\le200$ so far, and it abandons a chain as soon as a new term arrives later than the table says. We call a chain tight if every term $a_t$ stands at position $t=m(a_t)$, that is, if every initial part of it is a shortest chain for its last term. For example, $1,2,3,6,12,15$ is tight, because $m(2)=1$, $m(3)=2$, $m(6)=3$, $m(12)=4$ and $m(15)=5$. The chain $1,2,3,4,7$ is a shortest chain for $7$, but it is not tight: $4$ arrives at position $3$, while $m(4)=2$.

Claim: the test never abandons a tight chain whose terms are at most $200$. Every reached entry is the position of $x$ in a chain that the program has built, and the part of that chain up to $x$ is an addition chain for $x$, so an entry is never smaller than $m(x)$. A term $a_t$ of a tight chain arrives at position $t=m(a_t)$, which is never later than its entry.

The search therefore finds $m(k)$ for every $k$ that has a tight shortest star chain, once the depth limit reaches $m(k)$. This is a property of individual numbers, not a theorem: it fails at $12509$ at the latest, since that number has no shortest star chain at all. Exhaustive search confirms it for every $k\le3000$; for $15$, all four shortest chains $1,2,3,5,10,15$, $1,2,3,6,9,15$, $1,2,3,6,12,15$ and $1,2,4,5,10,15$ are tight star chains.

7. Deepening one step at a time

The program runs the search with the depth limits $D=1,2,3,\dots$, a method called iterative deepening: ^[7] sweep $D$ builds star chains of at most $D$ steps whose terms are at most $200$, and the table is kept from one sweep to the next.

Claim, using the verified fact of Section 6: after sweep $D$, the table holds $m(x)$ for every $x\le200$ with $m(x)\le D$ and nothing for the other numbers; moreover, sweep $D$ builds exactly the tight star chains of length at most $D$ with terms at most $200$. The proof is by induction on $D$; before the first sweep only $m(1)=0$ is known. Suppose that before sweep $D$ the table holds exactly the values $m(x)\le D-1$. A term $x$ at a position $t\le D-1$ has $m(x)\le t$, so its entry is exact, and the test abandons it exactly when $t\gt m(x)$. A term $x$ at position $D$ is abandoned exactly when $m(x)\lt D$: then its entry is $m(x)$, whereas for $m(x)=D$ the entry is still empty or already $D$. So sweep $D$ builds exactly the tight star chains of length at most $D$. By Section 6, every $x\le200$ with $m(x)=D$ ends one of them and receives the entry $D$, while no number with $m(x)\gt D$ can be reached in $D$ steps.

So the program may stop as soon as no entry is empty: at that moment the table is exact. For the limit $200$ this happens after sweep $11$, because $191$ is the smallest number with $m=11$ and $379$ the smallest with $m=12$. ^[6]

8. Worked example: the third sweep

Before sweep $3$ the table holds $m(1)=0$, $m(2)=1$ and $m(3)=m(4)=2$. The program tries the largest addend first. From $1$ it builds $1,2$, then $1,2,4$ and its continuations $1,2,4,8$, $1,2,4,6$ and $1,2,4,5$, whose last terms $8$, $6$ and $5$ receive the entry $3$. Then come $1,2,3$, $1,2,3,6$ and $1,2,3,5$; the last two tie with the table and are kept. Finally $1,2,3,4$ is abandoned, because $4$ arrives at position $3$ while its entry is $2$. Together with the chain $1$ itself, the sweep builds nine chains, exactly the tight star chains of length at most $3$.

Ties must be kept, because chains with the same last number can continue differently: $1,2,4,8,10$ and $1,2,4,5,10$ both reach $10$ in four steps, but only the second continues to $15=10+5$. A search that continued only the first chain to reach each number in a sweep would get $91$ of the $200$ values wrong, the first of them $m(15)$.

With the limit $20$, the six sweeps add the numbers $2$; $3,4$; $5,6,8$; $7,9,10,12,16$; $11,13,14,15,17,18,20$; and $19$, so the sum of $m(k)$ for $k\le20$ is

$$\begin{aligned}&1\cdot1+2\cdot2+3\cdot3\\&\quad+4\cdot5+5\cdot7+6\cdot1=75.\end{aligned}$$

How the Code Works

The C++ program ^[8] starts in main, which calls parse_arguments: --limit=N replaces the limit $200$ by a positive integer $N$, read into an int without an overflow check, --skip-checkpoints skips the checks, and other arguments are rejected. run_checkpoints then checks $m(15)=5$ in the table returned by minimal_multiplications(15) and the sum $26$ of Section 2 with solve(10). Finally the sum computed by solve is printed.

minimal_multiplications fills a std::vector<int> named best with std::numeric_limits<int>::max(), which means “not reached yet”, sets best[1] to $0$ and starts the current chain as {1}. It then calls dfs_chains with max_depth equal to $1,2,\dots,15$, the sweeps of Section 7, and stops after the first sweep that leaves no entry unreached. For limits up to $3000$ the table is complete after at most $15$ sweeps, by Sections 6 and 7, since no number below $3583$ needs $16$ multiplications; ^[6] from the limit $3583$ on, entries would stay unreached and solve would add the sentinel to the sum, an int overflow.

dfs_chains extends one chain, held in a vector; depth is the number of steps so far, and at the depth limit the function returns. Otherwise it forms the star steps of Section 5, next = last + chain[i] for i from depth down to $0$, so the largest addend comes first; by Section 7 the order does not change which chains a sweep builds. A candidate above the limit is skipped (Section 1), and so is a candidate with depth + 1 > best[next], the test of Section 6. Otherwise it lowers the entry if the new chain is shorter, appends the term, calls itself and removes the term again. Two further tests, next <= last and next == seen_prev, never fire, because the chain increases and the candidates of one call are all different.

The Python and Java versions run the same search with the fixed limit $200$ and without options or checkpoints. Python uses float('inf') for an unreached entry, a nested function dfs and a fresh list [1] in every sweep. Java keeps best as a static int[] filled with Integer.MAX_VALUE and the chain in an ArrayList<Integer>, and chain.remove(chain.size() - 1) removes the last term by its index. All values are small, so C++ and Java use plain int.

Complexity and Verification

By Section 7, sweep $D$ costs one call of dfs_chains for each tight star chain of length at most $D$ whose terms are at most the limit, each call tests at most $D$ candidates, and after the sweep the program scans the table for unreached entries. For the limit $200$ the eleven sweeps make $2$, $4$, $9$, $24$, $76$, $246$, $822$, $2749$, $9147$, $19583$ and $20910$ calls, $53\,572$ in all. Without the test of Section 6, the eleventh sweep alone would build $42\,755\,352$ star chains. A single sweep with the depth limit $11$ would also be correct, by the claim of Section 6, with $36\,376$ calls and $275\,400$ candidate tests instead of $53\,572$ and $321\,809$; the deepening costs a little more, but it tells the program when to stop. The memory is the table of $201$ entries, one chain of at most $12$ terms and at most $12$ nested calls, and on a desktop computer all three programs finish in a few hundredths of a second. The number of tight chains grows quickly with the limit: for the limit $1000$ the program needs $13$ sweeps and $1\,057\,387$ calls.

Before the main run, the C++ program checks $m(15)=5$ and the sum $26$ for $k\le10$. For this article, a separate search computed $m(k)$ for every $k\le3000$ from the definition alone: it tried the depths $\lceil\log_2k\rceil$, $\lceil\log_2k\rceil+1$, … with all sums of two terms and cut a chain only when doubling could no longer reach $k$, using neither star chains nor the table test. Its values agree with the first $100$ terms of OEIS A003313 ^[3] and with the smallest numbers that need $r$ steps in OEIS A003064 up to $1903$ for $r=15$. ^[6] With these values, a second enumeration that keeps only tight star chains reaches every $k\le3000$, which is the fact used in Sections 6 and 7. A copy of the program's search reproduces this table for every limit up to $1000$, with call counts equal to a direct count of tight star chains; the compiled C++ program prints the correct sum for every limit up to $200$, for example $50$ for the limit $15$, and the three programs print the same number. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The pruning test with tight chains, the description of each sweep and the counts of chains are derived explicitly in this article.

Project Euler 122 — Efficient Exponentiation. The official statement computes n¹⁵ with fourteen, six and five multiplications, defines m(k) as the minimum number of multiplications needed to compute nᵏ, so that m(15) = 5, and asks for the sum of m(k) for 1 ≤ k ≤ 200.
Wikipedia — Addition chain. The article defines addition chains, the binary and factor methods and Brauer or star chains, in which each sum uses the immediately previous number; Hansen showed that some n have no shortest star chain, the smallest being 12509. No algorithm is known that finds a minimal chain for a given number with guaranteed reasonable time or memory, and a generalised version for a sequence of values is NP-complete (Downey, Leong and Sethi).
OEIS A003313 — Length of shortest addition chain for n. Equivalently, a(n) is the minimal number of multiplications required to compute the n-th power; the entry lists 0, 1, 2, 2, 3, 3, 4, 3, 4, 4, … for n = 1, 2, 3, …
Wikipedia — Exponentiation by squaring. The binary method uses ⌊log₂ n⌋ squarings and one multiplication fewer than the number of ones in the binary expansion of n; 15 is the smallest exponent for which an addition chain does better, with 5 multiplications instead of 6.
MathWorld — Brauer Chain. A Brauer chain is an addition chain in which each member uses the previous member as an addend.
OEIS A003064 — Smallest number with shortest addition chain of length n. The terms for n = 0, 1, …, 16 are 1, 2, 3, 5, 7, 11, 19, 29, 47, 71, 127, 191, 379, 607, 1087, 1903 and 3583; for example, 191 is the smallest number that needs 11 steps.
Wikipedia — Iterative deepening depth-first search. A depth-limited depth-first search is run repeatedly with increasing depth limits; this finds the shallowest goal, as breadth-first search does, with much less memory.
C++ — Euler122.cpp. The linked immutable C++ revision contains dfs_chains, minimal_multiplications, solve and the checkpoints m(15) = 5 and 26 for the sum up to k = 10. It is the implementation record for this article.

Problem 122 source code

C++

#include <algorithm>
#include <array>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

namespace {

struct Options {
    int limit = 200;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 1;
}

void dfs_chains(const int max_depth,
                const int limit,
                std::vector<int>& chain,
                std::vector<int>& best) {
    const int depth = static_cast<int>(chain.size()) - 1;
    if (depth >= max_depth) {
        return;
    }

    const int last = chain.back();
    int seen_prev = -1;

    for (int i = depth; i >= 0; --i) {
        const int next = last + chain[static_cast<std::size_t>(i)];
        if (next > limit || next <= last) {
            continue;
        }
        if (next == seen_prev) {
            continue;
        }
        seen_prev = next;

        if (depth + 1 > best[static_cast<std::size_t>(next)]) {
            continue;
        }

        if (depth + 1 < best[static_cast<std::size_t>(next)]) {
            best[static_cast<std::size_t>(next)] = depth + 1;
        }
        chain.push_back(next);
        dfs_chains(max_depth, limit, chain, best);
        chain.pop_back();
    }
}

std::vector<int> minimal_multiplications(const int limit) {
    std::vector<int> best(static_cast<std::size_t>(limit + 1), std::numeric_limits<int>::max());
    best[1] = 0;

    std::vector<int> chain = {1};

    for (int max_depth = 1; max_depth <= 15; ++max_depth) {
        dfs_chains(max_depth, limit, chain, best);

        bool done = true;
        for (int k = 1; k <= limit; ++k) {
            if (best[static_cast<std::size_t>(k)] == std::numeric_limits<int>::max()) {
                done = false;
                break;
            }
        }
        if (done) {
            break;
        }
    }

    return best;
}

int solve(const int limit) {
    const std::vector<int> best = minimal_multiplications(limit);
    int sum = 0;
    for (int k = 1; k <= limit; ++k) {
        sum += best[static_cast<std::size_t>(k)];
    }
    return sum;
}

bool run_checkpoints() {
    const std::vector<int> best = minimal_multiplications(15);
    if (best[15] != 5) {
        std::cerr << "Checkpoint failed for m(15)" << '\n';
        return false;
    }
    if (solve(10) != 26) {
        std::cerr << "Checkpoint failed for sum up to 10" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.limit) << '\n';
    return 0;
}

Python

# Problem 122: Efficient exponentiation
# Find shortest addition chain for each k up to 200.

def solve():
    limit = 200
    best = [float('inf')] * (limit + 1)
    best[1] = 0
    
    def dfs(chain, max_depth):
        depth = len(chain) - 1
        if depth >= max_depth: return
        last = chain[-1]
        for i in range(depth, -1, -1):
            nxt = last + chain[i]
            if nxt > limit or nxt <= last: continue
            if depth + 1 > best[nxt]: continue
            if depth + 1 < best[nxt]:
                best[nxt] = depth + 1
            chain.append(nxt)
            dfs(chain, max_depth)
            chain.pop()
    
    for max_depth in range(1, 16):
        dfs([1], max_depth)
        if all(best[k] < float('inf') for k in range(1, limit + 1)):
            break
    
    print(sum(best[k] for k in range(1, limit + 1)))

solve()

Java

import java.util.*;

public class Euler122 {
    static int[] best;

    static void dfs(List<Integer> chain, int maxDepth, int limit) {
        int depth = chain.size() - 1;
        if (depth >= maxDepth)
            return;
        int last = chain.get(depth);
        for (int i = depth; i >= 0; i--) {
            int nxt = last + chain.get(i);
            if (nxt > limit || nxt <= last)
                continue;
            if (depth + 1 > best[nxt])
                continue;
            if (depth + 1 < best[nxt])
                best[nxt] = depth + 1;
            chain.add(nxt);
            dfs(chain, maxDepth, limit);
            chain.remove(chain.size() - 1);
        }
    }

    public static void main(String[] args) {
        int limit = 200;
        best = new int[limit + 1];
        Arrays.fill(best, Integer.MAX_VALUE);
        best[1] = 0;
        List<Integer> chain = new ArrayList<>();
        chain.add(1);
        for (int md = 1; md <= 15; md++) {
            dfs(chain, md, limit);
            boolean done = true;
            for (int k = 1; k <= limit; k++)
                if (best[k] == Integer.MAX_VALUE) {
                    done = false;
                    break;
                }
            if (done)
                break;
        }
        int sum = 0;
        for (int k = 1; k <= limit; k++)
            sum += best[k];
        System.out.println(sum);
    }
}