# Project Euler 122: Finding the most efficient exponentiation method.

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

### Posted by Kristian

Jean-Marie Hachey

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.

Kristian

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

CuongVM

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

Hossein

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

jjhangu

I did that
For 1 to 200

But you did it just one time~!
Good~!!!!

JuanTigg

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.

Richard

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 https://oeis.org/A003313/b003313.txt, 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.

Jean-Marie Hachey

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)
______
Sources:

2) Length of shortest addition chain for n. (A003313)
https://oeis.org/A003313

Jean-Marie Hachey

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

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

Hi Kristian,

After reading and debugging your code, I realized that the crucial part that makes your method work is this

depth > cost[power]

But I don’t understand why, for example we have these 2 chains:

1st: 1, 2, 4
2nd: 1, 2, 3, 4

According to your algorithm, 1st chain will be explored first and it will set min cost to number 4 is 3, but that’s just for number 4. When your algorithm explores the 2nd chain up to number 4, it sees that cost to number 4 is now 4 which is greater than the old cost which is 3, and it just stop that chain there.
So obviously that’s the right thing to do if you only want to explore up to number 4, but when we want to explore until a number greater than 4, why couldn’t it be the case that if we continue with 2nd chain it would give a shorter chain than if we go with the 1st chain?

Kristian

Hi Leo

I am pretty sure that for this specific example that would never be the case. If you wanted to generate 7 from this, you would need an additional two steps from the first chain, and only 1 step from the second chain. But that would make you end up at the same length.

If you want to reach 9, you would reach that both when branching out from 3 (3+3+3 two steps) and from (4+4+1 also two steps). So I believe it holds, unless you can come up with a counter example.

Carl J Appellof

I went to Knuth vol 3 “Seminumerical Algorithms” section 4.6.3 and following and constructed the “power tree” he suggests according to an algorithm detailed in Exercise 5. From that, I got a solution of 1584 in .06 ms. Now I have to figure out why you got a smaller result. There must be a couple of numbers between 1 and 200 that have smaller values.