Project Euler 122 - Efficient Exponentiation

Official link:

Thought Process

Problem is asking us to find the optimal Addition-Chain for all k < 200.

It has the corresponding OEIS sequence:

From OEIS there are lot's of helpful links such as the following: which gave me the idea for my code.

Essentially I build up a complete tree (with root node 1) of addition chains in a breadth-first search manner. This is helpful because it means that if I reach a value for the first time it is guaranteed that this is a shortest addition chain to that value.

I assert that my addition chain is strictly increasing which cuts down the search space by a lot, the reason for this is simply that if an addition chain is not increasing then it can be re-ordered.

I opted for the use of a stack. I include my code below with comments

Interactive Code

Input an Integer (yourinput)

Code will output sum(m(k)) for all 1 ≤ k ≤ yourinput