<div>The algorithm I would use:</div>
<div> </div>
<div>Treat the problem as a directed graph of 1 million vertices where each vertex has at most 1 outgoing edge. Each vertex is labeled with a number N(v).</div>
<div> </div>
<div>For each vertex v, if sum(divisors(N(v))) <= 1 million, that vertex has an outgoing edge to vertex v', where N(v') == sum(divisors(N(v))).</div>
<div> </div>
<div>Call this graph G0.</div>
<div> </div>
<div>1) 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> </div>
<div>If there are any such vertices in the graph, you can remove them. Call this new graph G1.</div>
<div> </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> </div>
<div>You can repeat this process until no such vertices remain. Call the final resultant graph Gn.</div>
<div> </div>
<div>Lemma 4) Each vertex in Gn has exactly 1 incoming edge and exactly 1 outgoing edge.</div>
<div>Proof:</div>
<div> 1) No vertex has 0 incoming edges or else we would have removed it above.</div>
<div> 2) Pidgeonhole principle: There are exactly as many edges as vertices. If any vertex had 2 incoming edges, there must be at least one vertex with 0 incoming vertices.</div>
<div> </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. Since Gn is finite and each vertex has exactly 1 incoming & 1 outgoing edge, eventually you will return to that vertex. This forms a cycle and there were no other possible edges to follow.
</div>
<div> </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. 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> </div>
<div>As to how to profile:</div>
<div>> ghc --make -auto-all -prof -O2 main.hs</div>
<div>> main +RTS -p</div>
<div>will generate a profile report in main.prof. I've found that functions that do a large amount of allocation tend to be the easiest to optimize. Adding additional strictness annotations (seq) sometimes helps.</div>
<div> </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> </div>
<div>as an alternative to the "IsSeen" maps that you might use to iteratively construct a graph.</div>
<div> </div>
<div>I'd probably use something like this:</div>
<div> </div>
<div>type Graph a = Map a Vertex</div>
<div>data Vertex a = Vertex a [Vertex a]</div>
<div> </div>
<div>instance Eq a => Eq (Vertex a) where</div>
<div> Vertex a _ == Vertex b _ = a == b</div>
<div> </div>
<div>then:</div>
<div>constructGraph :: Ord a => (a -> Graph a -> [Vertex a]) -> [a] -> Graph a</div>
<div>constructGraph mkEdges labels = graph where</div>
<div> graph = Map.fromList [(label, Vertex label (mkEdges label graph)) | label <- labels]</div>
<div> </div>
<div>Notice that graph is used in its own definition!</div>
<div> </div>
<div>You can picture this as first creating a map like this:</div>
<div>1 -> Vertex 1 _</div>
<div>2 -> Vertex 2 _</div>
<div>3 -> Vertex 3 _</div>
<div>...</div>
<div> </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, updating the "_" with pointers to the actual vertices.</div>
<div> </div>
<div> -- ryan</div>