{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a84baacf",
   "metadata": {},
   "source": [
    "# [Amicable Chains](https://projecteuler.net/problem=95)\n",
    "\n",
    "Numbers that form an amicable chain are called [sociable numbers](https://en.wikipedia.org/wiki/Sociable_number). Interestingly, the [Catalan-Dickson conjecture](https://en.wikipedia.org/wiki/Aliquot_sequence) posits that *every* starting number eventually reaches either 0 or a sociable number.\n",
    "\n",
    "Regardless, we can find these chains very cleanly, albeit somewhat slowly, with SageMath's graph tooling and `divisors` function. Simply add a directed edge from every number to its aliquot sum, assuming both are below 1000000."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f047494c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Looped digraph on 965607 vertices (use the .plot() method to plot)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "limit = 1000000\n",
    "G = DiGraph(loops=True)\n",
    "for n in range(1, limit + 1):\n",
    "    s = sum(divisors(n)) - n\n",
    "    if s <= limit:\n",
    "        G.add_edge(n, s)\n",
    "        \n",
    "G"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38ac2d0e",
   "metadata": {},
   "source": [
    "Once the graph is constructed, just iterate through all the cycles to get to the largest one, and get its smallest number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8527e13c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14316"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_cycle = None\n",
    "for cycle in G.all_cycles_iterator(simple=True):\n",
    "    longest_cycle = cycle\n",
    "    \n",
    "min(longest_cycle)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bf72629",
   "metadata": {},
   "source": [
    "Another interesting fact: the amicable chain we've found here is not just the longest chain composed of numbers below 1000000 - it's actually the longest known amicable chain, *period*.\n",
    "\n",
    "## Relevant sequences\n",
    "* Smallest members of amicable chains: [A003416](https://oeis.org/A003416)\n",
    "* The amicable chain containing this problem's answer: [A072890](https://oeis.org/A072890)\n",
    "\n",
    "#### Copyright (C) 2025 filifa\n",
    "\n",
    "This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}