Problem 14

The following iterative sequence is defined for the set of positive integers:

n n/2 (n is even)
n 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 40 20 10 5 16 8 4 2 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

訳

正の整数に対して，以下の帰納的な数列を考える．

n n/2 (nは偶数)
n 3n + 1 (nは奇数)

このルールを使って，13から始めると

13 40 20 10 5 16 8 4 2 1

なる列を得る．

この列（13から始まって1で終わる）は10項からなり，まだ証明されていない（コラッツ予想）が任意の正の整数から始めて1で終わると思われている．

1000000以下の数で，もっとも長い列を作る数は何か．

ただし，1000000以下の数であっても列の長さ初めても途中の項は1000000を超えることはありうる．

Haskell：シンプルな方法

{-
Project Euler Problem 14 e14.hs
-}

collatz::Integer -> [Integer]
collatz n
    | n == 1    = [1]
    | otherwise = n:((collatz.next) n)
      where next:: Integer->Integer
            next n 
                | n `mod` 2 == 0 = n `div` 2
                | otherwise      = 3*n+1

collatsLengthList::[Integer] -> [(Integer, Integer)]
collatsLengthList = (map (\x -> (head x, (toInteger.length) x))) . (map collatz) 

getMax::[(Integer, Integer)] -> Integer
getMax = maximum . map (\x -> snd x)

answer n =  filter (\x -> snd x == max) ns
    where ns = collatsLengthList [1..n]
          max = getMax ns

各々の数に対して，実際にコラッツの列を生成して，もとの数と列の長さをタプルにします．そして，長さ最大のものを探し出すというだけです．

けどこれ，10000くらいまでならいいですが，100000だと時間がかかって駄目ですし，1000000は論外です．明らかな無駄があります．