Problem 122 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Problem 122 へ行く。
• Problem 122 の差分を削除

#author("2021-10-24T11:35:07+00:00","","")
#author("2021-10-24T11:36:32+00:00","","")
*[[Problem 122:http://projecteuler.net/problem=122]] 「効率的なべき乗計算」 [#yf9288c3]

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

>>> n × n × ... × n = &tex{n^{15}};

しかし2進法を用いれば, 6 回の掛け算で計算できる.

>>> n × n = &tex{n^{2}};~
&tex{n^{2}}; × &tex{n^{2}}; = &tex{n^{4}};~
&tex{n^{4}}; × &tex{n^{4}}; = &tex{n^{8}};~
&tex{n^{8}}; × &tex{n^{4}}; = &tex{n^{12}};~
&tex{n^{12}}; × &tex{n^{2}}; = &tex{n^{14}};~
&tex{n^{14}}; × n = &tex{n^{15}};

ところがたった 5 回の掛け算のみでも計算できる.

>>> n × n = &tex{n^{2}};~
&tex{n^{2}}; × n = &tex{n^{3}};~
&tex{n^{3}}; × &tex{n^{3}}; = &tex{n^{6}};~
&tex{n^{6}}; × &tex{n^{6}}; = &tex{n^{12}};~
&tex{n^{12}}; × &tex{n^{3}}; = &tex{n^{15}};

m(&tex{k};)を &tex{n^{k}}; を求めるのに必要最低限な掛け算の回数と定義する.
たとえば m(15)=5 である.

1 ≤ &tex{k} ≤ 200 に対し, Σ m(&tex{k}) を求めよ.
1 ≤ &tex{k}; ≤ 200 に対し, Σ m(&tex{k};) を求めよ.

IP:183.176.112.9 TIME:"2021-10-24 (日) 20:36:32" REFERER:"http://odz.sakura.ne.jp/projecteuler/index.php" USER_AGENT:"Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:93.0) Gecko/20100101 Firefox/93.0"