Amicable Chains¶

Numbers that form an amicable chain are called sociable numbers. Interestingly, the Catalan-Dickson conjecture posits that every starting number eventually reaches either 0 or a sociable number.

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.

In [1]:
limit = 1000000
G = DiGraph(loops=True)
for n in range(1, limit + 1):
    s = sum(divisors(n)) - n
    if s <= limit:
        G.add_edge(n, s)
        
G
Out[1]:
Looped digraph on 965607 vertices (use the .plot() method to plot)

Once the graph is constructed, just iterate through all the cycles to get to the largest one, and get its smallest number.

In [2]:
longest_cycle = None
for cycle in G.all_cycles_iterator(simple=True):
    longest_cycle = cycle
    
min(longest_cycle)
Out[2]:
14316

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.

Relevant sequences¶

  • Smallest members of amicable chains: A003416
  • The amicable chain containing this problem's answer: A072890

Copyright (C) 2025 filifa¶

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.