Efficient exponentiation

The most naive way of computing n¹⁵ requires fourteen multiplications:

n × n × ... × n = n¹⁵

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

n × n = n²n² × n² = n⁴n⁴ × n⁴ = n⁸n⁸ × n⁴ = n¹²n¹² × n² = n¹⁴n¹⁴ × n = n¹⁵

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

n × n = n²n² × n = n³n³ × n³ = n⁶n⁶ × n⁶ = n¹²n¹² × n³ = n¹⁵

We shall define m(k) to be the minimum number of multiplications to compute n^k; for example m(15) = 5.

For 1 ≤ k ≤ 200, find ∑ m(k).

Written by gamwe6 who lives and works in San Francisco building useful things. You should follow him on Twitter