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 computingn^{15}requires fourteen multiplications:

nxnx … xn=n^{15}

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

nxn=n^{2}

n^{2}xn^{2}=n^{4}

n^{4}xn^{4}=n^{8}

n^{8}xn^{4}=n^{12}

n^{12}xn^{2}=n^{14}

n^{14}xn=n^{15}

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

nxn=n^{2}

n^{2}xn=n^{3}

n^{3}xn^{3}=n^{6}

n^{6}xn^{6}=n^{12}

n^{12}xn^{3}=n^{15}

We shall define m(k) to be the minimum number of multiplications to computen^{k}; 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

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.

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

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

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

I did that

For 1 to 200

But you did it just one time~!

Good~!!!!

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.

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.

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:

1) http://www.mathblog.dk/files/euler/Problem122.cs

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

https://oeis.org/A003313

Correction:

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

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?

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.

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.