Effiziente Potenzierung

Problem 122

Der naivste Weg, n15 zu berechnen, erfordert vierzehn Multiplikationen:

n × n × ... × n = n15

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

n × n = n2
n2 × n2 = n4
n4 × n4 = n8
n8 × n4 = n12
n12 × n2 = n14
n14 × n = n15

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

n × n = n2
n2 × n = n3
n3 × n3 = n6
n6 × n6 = n12
n12 × n3 = n15

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

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