Der einfachste Weg, n15 zu berechnen, benötigt vierzehn Multiplikationen:

n × n × ... × n = n15

Durch die "binäre" Methode kann man es mit 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 Schritten zu berechnen:

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

Die Funktion m(k) definiert die geringste benötigte Anzahl von Multiplikationen, um nk zu berechnen. Im Beispiel ist also m(15) = 5.

Finden Sie m(k), wobei 1 ≤ k ≤ 200.

Diese Aufgabe auf projecteuler.net