Project Euler 122 - Efficient Exponentiation

Official link: https://projecteuler.net/problem=122

Thought Process

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

It has the corresponding OEIS sequence: https://oeis.org/A003313

From OEIS there are lot's of helpful links such as the following: https://wwwhomes.uni-bielefeld.de/achim/addition_chain.html 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