115 lines
3.2 KiB
Plaintext
115 lines
3.2 KiB
Plaintext
{
|
|
"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
|
|
}
|