Effiziente Potenzierung

Der naivste Weg, n¹⁵ zu berechnen, erfordert vierzehn Multiplikationen:

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

Aber mit der "binären" Methode kann man es in sechs Multiplikationen berechnen:

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

Es ist jedoch möglich, es in nur fünf Multiplikationen zu berechnen:

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

Wir definieren m(k) als die geringste benötigte Anzahl von Multiplikationen, um n^k zu berechnen; zum Beispiel m(15) = 5.

Finden Sie ∑ m(k) für 1 ≤ k ≤ 200.