122 : 効率的なべき乗計算

$n^{15}$を求めるのに最も単純な方法では 14 回の掛け算が必要である.

$n × n × \dots × n = n^{15}$

しかし、2進法を用いれば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$である.

$1 ≤ k ≤ 200$に対し、$\sum m(k)$を求めよ.