# Project Euler #122: Efficient exponentiation

# Project Euler #122: Efficient exponentiation

+ 2 comments The solution is not unique. For the given sample test case of 15, we have the following:

n^1 * n^1 = n^2

n^2 * n^2 = n^4

n^4 * n = n^5

n^5 * n^5 = n^10

n^10 * n^5 = n^15

So, how are we supposed to know which version to print? So I think this is not properly solvable.

+ 1 comment please supply me with a few testcases. I find nothing wrong with my code till now.

+ 1 comment Was having trouble with the use of brauer chain (wasn't sure brauer chain necessarily contains one of the shortest chains for every , but it satisfies the input contraint here). Implemented some sort of breadth first search with

`deque`

and got Runtime Error #2.With a bit of tweaking, I found that for certain input range there must be a shortest chain starting with

`[1, 2, 4, 8, 16]`

, and some smaller range`[1, 2, 4, 8]`

. This reduces the queue significantly. Then it passed. Smells like cheating.

+ 0 comments Hope this is not spoiler on contest. I think it is not, but if admins think it is, feel free to delete.

Gotta say the expert who did handpick the test cases must be some kind of evil genius. Thanks. Got me delving bit deeper into this, since you just happened to pick some cases where Donald Knuth's power tree method fails to create the most optimal chain. There are not many numbers below 10000 where this method fails for creating the optimum chain. Well, Knuth tells in his book what are the numbers. Method itself is blazingly fast.

BUT. Can anyone elaborate WHY power tree method fails on these numbers? My understanding on subject is not enough. Tried to think about it and cant see the reason.

+ 1 comment It is giving a runtime error in test case. While I have run this range 2<=2<=275 and did not get any runtime error. Its only when I submit the code.

I really doubt this error. Could you help me out here.

Sort 11 Discussions, By:

Please Login in order to post a comment