Ruby でコラッツの問題
ja.wikipedia.org
「コラッツの問題」というのは、自然数 n を取り、
- n が偶数なら2で割る
- n が奇数なら、3倍して1を足す
という操作を繰り返したところ、どうなるかという問題。じつはこれは難問で、いまだに解決されていない。いまのところ、初期値が268あたりまで、1に帰結することが知られているそうである。
Ruby で計算してみる。初期値が10万までの範囲での、1に至るステップ数の最大値を求めるコードを、再帰で実装する。
def collatz(n, co = 0) return co if n == 1 n.even? ? collatz(n / 2, co + 1) : collatz(3 * n + 1, co + 1) end puts (1..10_0000).map(&method(:collatz)).max #=>350
最大値は350ステップとわかる。実行時間は、僕の環境で0.94秒ほどでした。
350ステップかかるときの初期値を求めてみる。コードの後半をこう書き直す。
max = 0 max_idx = 1 (1..10_0000).each do |i| step = collatz(i) if step > max max = step max_idx = i end end p [max_idx, max] #=>[77031, 350]
初期値が77031のとき350ステップかかることがわかる。
追記
メモ化できるよう、コードを修正してみる。
$memo = {} def collatz(n) return $memo[n] if $memo[n] return 0 if n == 1 sum = n.even? ? collatz(n / 2) : collatz(3 * n + 1) $memo[n] = sum + 1 end puts (1..10_0000).map(&method(:collatz)).max #=>350
これだと0.12秒で済む。100_0000
回までやっても1.5秒ほど、ちなみに初期値が837799のとき、最大値524ステップを取る。もう一桁上げて、1000_0000
回までやると、初期値8400511のとき、最大値685ステップ。