---

Problem 122

---

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

---

高效指数计算

计算n¹⁵最朴素的方式需要14次乘法：

n × n × … × n = n¹⁵

但使用一个“二进制”的算法，你可以只用6次乘法：

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

然而，实际上仅用5次乘法也是可以的：

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

记m(k)是计算n^k所需要的最少次数，例如m(15) = 5。

对于1 ≤ k ≤ 200，求∑m(k)。

---