コラッツの続き

コメントありがとうございます＞なかださん
というわけで、||=を使ったりして、私の満足行くところまで短くなったプログラムを以下に:

class Collatz 
  include Enumerable
  def initialize( n )
    @n=n
    @cache={1=>1}
  end

  def calc(n)
    @cache[n] ||= 1+calc( 0==n%2 ? n/2 : n*3+1 )
  end
  
  def each
    (1..@n).each{ |n| yield [n,calc(n)]  }
  end
end

def collatz(n)
  Collatz.new(n).max{ |a,b| a[1]<=>b[1] }[0]
end

p collatz(100)

max_by は私の手元の処理系(ruby 1.8.4 (2005-12-24) [i386-mswin32])には入ってなかったので max のままにした。残念。

それと。先日(d:id:Nabetani:20060711)「偶数ぐらいとばした方が良かったか」と書いたのは、私の所謂数学的直感*1って奴が、偶数はとばしていいよ、と言っていたからなんだが、偶数を全部とばすと正しい結果が得られない。
飛ばしていいの偶数ではなく、6 で割った余りが 2,4,5 の場合（ただし、6で割った商が0の場合はその限りではない）。
理由は簡単で

• 4i+2 → 12i+4 → 6i+2
• 2i+1 → 6i+4
• 4i+3 → 12i+10 → 6i+5

というように、6i+2, 6i+4, 6i+5 は、それぞれよりも小さな値から始まる列に含まれるから。
それと。上記のプログラムで collatz(54) を計算すると 54 になるので、偶数を飛ばしてはいけないことは明らか。

というわけで、直感をむやみと信頼してはいけないよ、という当たり前の話が今回の教訓なのであった。

*1:直感 じゃなくて、直観かな?