가장 단순하게 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¹⁵

그러나 곱셈 횟수를 더 줄여서 다섯 번만에 계산하는 방법도 있습니다.

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

이제 n^k 의 계산에 필요한 곱셈의 최소 횟수를 m(k)라 하겠습니다. 예를 들어 m(15) = 5 입니다.

1 ≤ k ≤ 200 일 때, ∑ m(k) 를 구하세요.

(번역 도움: cfranck님)