<div dir="ltr"><br>I tried to solve the same problem and came out with a O(log n) solution. It is pretty quick, since I keep track of the steps on a map structure.<br><br>Even though it runs really fast, it hogs on memory just like Steve's version.<br>
<br>Following is the full source, for your consideration:<br><br><br>======================Euler14.hs======================<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">import qualified Data.Map as Map</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">import qualified Data.List as List</span><br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">type Table=Map.Map Integer Integer</span><br style="font-family: courier new,monospace;">
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">rank::Table->Integer->(Table,Integer)</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">rank s n= (s',r)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> where</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> nxt=if even n then (n `div` 2) else (3*n+1)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> r=case (Map.lookup n s) of</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> Just a -> a</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> Nothing-> (1 + (snd $ rank s nxt))</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> s'=Map.insert n r s</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"><br>search::Integer->Integer</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">search n = case List.findIndex (\a -> a==ms) sw of</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> Just a -> toInteger(a) +1</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> Nothing -> -1</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> where s=Map.singleton 1 1</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> sw=searchWork s [1..n]</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> ms=maximum sw</span><br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">searchWork::Table->[Integer]->[Integer]</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">searchWork s []=[]</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">searchWork s (i:is)= r:(searchWork s' is)</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> where</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> (s',r)=rank s i</span><br style="font-family: courier new,monospace;">
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">main = do </span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> print $ search 1000000</span><br style="font-family: courier new,monospace;">
======================Euler14.hs======================<br><br>
</div>