On Mon, Mar 31, 2008 at 6:00 PM, Bruno Carnazzi
I've done this modification with no more success :
import qualified Data.List as List import qualified Data.Map as Map
f :: Integer -> Integer
f n | even n = n `div` 2 | otherwise = 3 * n + 1
chain m n = let chain' cn cm | Map.member cn m = Map.map (+ (m Map.! cn)) cm | otherwise = chain' (f cn) $! Map.insert cn 1 (Map.map (+1) cm) in chain' n Map.empty
This function raises a red flag for me. The collatz sequence gets _very_ big, with very many distinct numbers. You are saving the length of the resulting chain for each of those numbers, which is going to take a lot of memory. But Map is also lazy in its values, so the values you are storing once chain finishes will look like: 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1 Instead of 22, which is taking quite a lot of memory as well. My impression is that the caching approach is just a bad idea. It is not necessary to solve the problem efficiently; a brute force approach runs in under 1 minute in constant memory for me. Try to simplify your approach. I'd suggest generating a list representing the collatz sequence starting at the number, then just taking its 'length'. Do that for each number and find the maximum. There should be no need for Data.Map. Luke