Project Euler No. 14

Problem

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

$n \rightarrow \frac{n}{2} $($n$ is even)
$n \rightarrow 3n + 1$ ($n$ is odd)

Using the rule above and starting with 13, we generate the following sequence:
$13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 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.

Code in Haskell

Euler_014.hs

module Main where
import Data.List

collatz n	
  | even n = div n 2
  | otherwise = 3*n+1

-- collatzSeries n = (takeWhile (/=1) $iterate collatz n)++[1]
collatzLength n = 1+ (count (/=1) $ iterate collatz n)
  where
    count cond [] = 0
    count cond (x:xs)
      | cond x = 1 + count cond xs
      |otherwise = 0

main = print $ (flip lookup) collatzLL $ maximum $ map fst collatzLL
  where collatzLL = [ (collatzLength a, a) | a<-[1..999999]]

Answer

8****9

Comments

相変わらず遅い（-Oオプションで6秒）。うーん。先行き不安だ。何かがおかしいのだと思うが、これもどうすればいいかはよくわからん。nのCollatz列長を求める際に、列の途中でnより小さいmに行き当たったら、それ以上計算せずにmの列長を返して加算するようにすれば効率化するのかもしれない。