<div>The algorithm I would use:</div>
<div>&nbsp;</div>
<div>Treat the problem as a directed graph of&nbsp;1 million vertices where each vertex has&nbsp;at most&nbsp;1 outgoing edge.&nbsp; Each vertex&nbsp;is labeled with a number&nbsp;N(v).</div>
<div>&nbsp;</div>
<div>For each vertex v, if sum(divisors(N(v)))&nbsp;&lt;= 1 million, that vertex has an outgoing edge to vertex v&#39;, where N(v&#39;) == sum(divisors(N(v))).</div>
<div>&nbsp;</div>
<div>Call this graph G0.</div>
<div>&nbsp;</div>
<div>1)&nbsp;No vertex with 0 incoming edges can be part of an amicable chain.</div>
<div>2) No vertex with 0 outgoing edges can be part of an amicable chain.</div>
<div>&nbsp;</div>
<div>If there are any such vertices in the graph, you can remove them.&nbsp;&nbsp;Call this new graph G1.</div>
<div>&nbsp;</div>
<div>Lemma 3) G1 is a directed graph where every vertex has at most one outgoing edge.</div>
<div>Proof) G0 has this property and we have only deleted vertices from G0, which can only remove the </div>
<div>&nbsp;</div>
<div>You can repeat this process until no such vertices remain.&nbsp; Call the final resultant graph Gn.</div>
<div>&nbsp;</div>
<div>Lemma 4) Each vertex in Gn has exactly 1 incoming edge and exactly 1 outgoing edge.</div>
<div>Proof:</div>
<div>&nbsp;&nbsp; 1) No vertex has 0 incoming edges or else we would have removed it above.</div>
<div>&nbsp;&nbsp; 2) Pidgeonhole principle:&nbsp; There are exactly as many edges as vertices.&nbsp; If any&nbsp;vertex had 2 incoming edges, there must be at least one vertex with 0 incoming vertices.</div>
<div>&nbsp;</div>
<div>Leamma 5) Each vertex in Gn is part of exactly one cycle.</div>
<div>Proof) Follow the outgoing vertex chain from a vertex.&nbsp; Since Gn is finite and each vertex has exactly 1 incoming&nbsp;&amp; 1 outgoing edge, eventually you will return to that vertex.&nbsp; This forms a cycle and there were no other possible edges to follow. 
</div>
<div>&nbsp;</div>
<div>Therefore: Algorithm:</div>
<div>1) Generate G0</div>
<div>2) Iteratively remove vertices from G0 to create G1, G2, etc. until there are no vertices with 0 incoming or outgoing edges.&nbsp; Let this graph be Gn</div>
<div>3) Split the vertices of Gn into equivalence classes where each class represents a cycle</div>
<div>4) Find the largest equivalence class.</div>
<div>5) Find the smallest label in that equivalence class.</div>
<div>&nbsp;</div>
<div>As to how to profile:</div>
<div>&gt; ghc --make -auto-all -prof -O2 main.hs</div>
<div>&gt; main +RTS -p</div>
<div>will generate a profile report in main.prof.&nbsp; I&#39;ve found that functions that do a large amount of allocation tend to be the easiest to optimize.&nbsp; Adding additional strictness annotations (seq) sometimes helps.</div>

<div>&nbsp;</div>
<div>For constructing graphs, you may want to look at <a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www.haskell.org/haskellwiki/Tying_the_Knot" target="_blank">http://www.haskell.org/haskellwiki/Tying_the_Knot
</a></div>
<div>&nbsp;</div>
<div>as an alternative to the &quot;IsSeen&quot; maps that you might use to iteratively construct a graph.</div>
<div>&nbsp;</div>
<div>I&#39;d probably&nbsp;use something like this:</div>
<div>&nbsp;</div>
<div>type Graph&nbsp;a = Map&nbsp;a Vertex</div>
<div>data Vertex&nbsp;a&nbsp;= Vertex&nbsp;a [Vertex a]</div>
<div>&nbsp;</div>
<div>instance Eq a =&gt; Eq (Vertex a) where</div>
<div>&nbsp; Vertex a _ == Vertex b _ = a == b</div>
<div>&nbsp;</div>
<div>then:</div>
<div>constructGraph :: Ord a =&gt; (a -&gt; Graph a -&gt; [Vertex a]) -&gt; [a] -&gt; Graph a</div>
<div>constructGraph mkEdges labels = graph where</div>
<div>&nbsp; graph = Map.fromList [(label, Vertex label (mkEdges label graph)) | label &lt;- labels]</div>
<div>&nbsp;</div>
<div>Notice that graph is used in its own definition!</div>
<div>&nbsp;</div>
<div>You can picture this as first creating a map like this:</div>
<div>1 -&gt; Vertex 1 _</div>
<div>2 -&gt; Vertex 2 _</div>
<div>3 -&gt; Vertex 3 _</div>
<div>...</div>
<div>&nbsp;</div>
<div>Then when you query the map for the edges of Vertex 2, only then does the mkEdges get called, with the constructed graph as input,&nbsp;updating the &quot;_&quot; with&nbsp;pointers to the actual vertices.</div>
<div>&nbsp;</div>
<div>&nbsp;-- ryan</div>