今回のテーマは「コラッツの問題」
・問題
1より大きい自然数nが与えられたときに
このnに対して次の操作を繰り返し行い
結果が1になるまで続ける
(a) nが奇数 → この数に1を加える
(b) nが偶数 → この数を2で割る
この操作で1に到達するまでに必要な回数をf(n)とすると
1からNまでの自然数nに対するf(n)の和をg(N)とする
g(32)の値を求めよ
結構有名なコラッツの問題を基にした簡易バージョン
このルールだと2進数で考えるのがかなり楽かもですが、
それを発想できるかが難しい。
2進数で考える方法だと……
・一番下の桁が1なら+1
・一番下の桁が0ならその0を消去（ = 右に1桁ずらす）
これを繰り返して1にすればOKですな。
f(2n) = f(n)+1 と f(2n-1) = f(n)+2 から
f(2n-1) = f(2n)+1 が成り立つので
奇数と偶数のときに分けて計算すれば簡単かな。
あとは2の乗数による切り替えのタイミングに
注意して書き出してみた方がチェックできて良いかも。
PR
