Задача 122
Эффективный метод возведения в степень

Наиболее простой способ нахождения n^(15) требует выполнения 14 умножений:

n × n × ... × n = n^(15)

Если воспользоваться "двойным" методом, n^(15) можно найти, выполнив 6 умножений:

n × n = n^(2)
n^(2) × n^(2) = n^(4)
n^(4) × n^(4) = n^(8)
n^(8) × n^(4) = n^(12)
n^(12) × n^(2) = n^(14)
n^(14) × n = n^(15)

Однако, количество умножений можно еще уменьшить – до 5 умножений:

n × n = n^(2)
n^(2) × n = n^(3)
n^(3) × n^(3) = n^(6)
n^(6) × n^(6) = n^(12)
n^(12) × n^(3) = n^(15)

Определим m(k) как минимальное количество умножений для нахождения n^(k). К примеру, m(15) = 5.

Найдите m(k) для 1 ≤ k ≤ 200.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net