Concurrent Clean : L.L.Ring : Collatz予想の収束

プログラミング

本当はRound 2は観戦にしておこうと思っていたのだけれど、
http://idm.s9.xrea.com/ratio/2006/07/12/000484.html
を見て、なにか挑戦された気がしたので、結局書いた。
何を挑戦された気がしたかというと、「問題を読み替えないで実装するためには、副作用が必須だ」という主張（というように私は理解したのだけど、間違っていたらごめん）。だから、純粋関数型だと読み替えないで実装するのは難しいのじゃない？（意訳）というような内容をみて、「これは挑戦に違いない」と勝手に思い込んだのでした。

      • -

まずは、Collatz予想の１ステップ分の関数定義。これはシンプルに。

f 1            = 1
f n | isEven n = n/2
               = 3*n + 1

さて、これをどうすれば言いかというと、Cleanには（そしてHaskellにも）、与えられた関数を何度も適用しながら、その結果をリストとして返すという便利な関数があるので、それを使って数列を生成します。

collatz n = iterate f n

たとえば、n=3のときは、次のような数列（リスト）が生成されます。

collatz 3 -> [3,10,5,16,8,4,2,1,1,1,...]

数列が得られたら、あとは収束する（値が１になる）までの部分数列を取り出して、その長さを数えれば、収束までのステップ数が得られます。

g n = length $ takeWhile ((<>) 1)
             $ collatz n

後は、任意の検索区間に対して、関数gを順次適用して、最大のステップ数を求めるだけ。

h n = maxList $ map g [1..n]

Start = h 100

お粗末様でした。

      • -

最後が、題意を間違えていたので、修正です。

h n = fst $ maxListBy cmp [(x,g x) \\ x <- [1..n]]
  where
    cmp (_,a) (_,b) = a < b

Start = h 100

元のだと、収束するまでの数列の長さそのものを表示していたので。