Project Euler 122: Finding the most efficient exponentiation method.

Project Euler 122: Finding the most efficient exponentiation method.

Written by on 10 November 2012

Topics: Project Euler

Problem 122 of Project Euler has really proved troublesome for me, partly because I couldn’t read the material I got. But I will get back to that after the problem statement.

The most naive way of computing n15 requires fourteen multiplications:

n x n x … x n = n15

But using a “binary” method you can compute it in six multiplications:

n x n = n2
n2 x n2 = n4
n4 x n4 = n8
n8 x n4 = n12
n12 x n2 = n14
n14 x n = n15

However it is yet possible to compute it in only five multiplications:

n x n = n2
n2 x n = n3
n3 x n3 = n6
n6 x n6 = n12
n12 x n3 = n15

We shall define m(k) to be the minimum number of multiplications to compute nk; for example m(15) = 5.

For 1  k  200, find ∑ m(k).

I didn’t have a really good idea on how to solve this, so I started looking for help on google, and found this page on Wikipedia about Addition-chain exponentiation. Which is exactly what we are looking for. Here it is stated that the problem is a well known NP-complete problem and therefore I knew that there would be no shortcuts if I just had to find a single value.

However, I thought I could use dynamic programming for solving it, since I needed all the smaller values as well. It wasn’t until after I build a solution (which later turns out to give me a value only 2 off the correct answer), that I came to the conclusion that the problem cannot be split into independent subproblems. It was only after that I discovered that the aforementioned wiki page tells me exactly that.

So after the detour, I decided to try a method where I generate a tree of solutions by combining all previously built solutions. The easiest way to approach this was through a recursive function where I keep track of the number of steps already taken as well as the path we are currently in. Then I explore the path until I reach the limit of 200 and then starting to backtrack and branch out.

So lets go through the algorithm (or part of it, for k ≤ 10). So We start at 1 and each time we do a binary exponentiation such taht we take the number we just got and double it. That means we will go on till we hit 16, which is the first number which is larger than out limit. For each number we generate we keep track of the path length to reach it in an array.

Once we hit 16 we start backtracking. So we go back to 8 and add the number prior to that, which is four and check the result. We do that until we reach a number which is smaller than our limit.

So when we hit 8+1 we are finally smaller than the limit, and we will continue out of that path. So our path right now is 1,2,4,8,9. Once again we will hit an awful lot of number larger than the limit.

Among them one interesting, the number 10. We have already seen that before. However the path to get to 10 is longer than last time we reached it, so we wont update the path length. We have now used all options to generate numbers from the path going to 8, so we will backtrack to 4 and start expanding the tree there. That will include the child node 6 which can then be expanded.

Since the tree contains 1, we can prove that we will generate all numbers less than the limit at some point. However, I don’t want to do that right here.

Once we have generated the whole tree all we need is to sum up the array of path lengths.

The tree generator can be implemented as

public void Backtrack(int power, int depth) {
    if (power > limit || depth > cost[power]) return;
    cost[power] = depth;
    path[depth] = power;
    for (int i = depth; i >= 0; i--)
        Backtrack(power + path[i], depth + 1);

The rest of the code can be seen in the source code. Once we execute the code it runs in just under 3ms on my machine. And we get the result

the sum of m is 1582

9 Comments For This Post I'd Love to Hear Yours!

  1. Jean-Marie Hachey says:

    Hi Kristian,

    In the example above, we saw that m(15) = 5.
    (Minimum number of multiplications to compute n^k).

    Taking in account different possibilities of exponentiation, what about the maximum of multiplications to compute n^k in the same example ?
    (There is a possibility of a total of 8 combinations of exponentiation leading to 15.)

    1) a x a = a^2
    2) a^2 x a = a^3
    3) a^3 x a^2 = a^5
    4) a^5 x a^5 = a^10
    5) a^10 x a^5 = a^15

    1) a x a = a^2
    2) a^2 x a = a^3
    3) a^3 x a^3 = a^6
    4) a^6 x a^3 = a^9
    5) a^9 x a^6 = a^15

    Etc, …

    Thanks for the problem.

  2. Kristian says:

    You should be able to change the code to track that as well, but it will take some changes of the code.

  3. CuongVM says:

    I run the code… the sollution is correct for 12<= m <= 200 :)) I get the other numbers from wiki :)))

  4. Hossein says:

    Ahh Damn !

    I am getting 1584 too 🙁

    my method does look for all previous chains and seeks whether is it avail able for a chain to obtain two powers from it an by one step reach the answer or not

  5. jjhangu says:

    I did that
    For 1 to 200

    But you did it just one time~!

  6. JuanTigg says:

    Inefficient, using a backtrack it’s time-expensive, search-in-depth algorithm. How will you solve the problem when having a 128 or 256 -bit number? Since it’s a NP-complete problem the only feasible solution is to use heuristics. Neil Clift has studied addition chains for a while and has proved that the Scholz-Brauer conjecture holds for n < 5784689.

  7. Richard says:

    I wrote a program in C to solve this problem, based on your diagrams but not using your code. It solved the problem in 5 msec. For k up to 7000 it took 525 seconds. The solution for 7000 was verified from the list at, which lists values up to k= 1000000

    So I conclude that your algorithm is sound for k<5784689. Judging from the comments in the thread for problem 122 it is difficult to improve on this performance.

  8. Jean-Marie Hachey says:

    Some values of k and ∑ m(k) calculated with Kristian’s algo (1)

    k (∑ m(k)); t(ms)
    200 (1582); 12
    300 (2593); 31
    500 (4785); 146
    1000 (10808); 1235
    2000 (24063); 12542


    The last five lines in OEIS A003313 sequence (2):

    k (∑ m(k))
    99996 (20)
    99997 (21)
    99998 (21)
    99999 (21)
    100000 (20)


    2) Length of shortest addition chain for n. (A003313)

  9. Jean-Marie Hachey says:

    In my last comment, this line:
    The last five lines in OEIS A003313 sequence (2):
    k (∑ m(k))

    should read:
    The last five lines in OEIS A003313 sequence (2):
    k (m(k))

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.