Problem #95 says:
The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.
Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.
Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:
12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)
Since this chain returns to its starting point, it is called an amicable chain.
Find the smallest member of the longest amicable chain with no element exceeding one million.
An extremely easy problem to solve despite the fact that it’s quite far down the list when sorted by difficulty. We can instantly stop generating the chain if it exceeds one million at any point in the chain. Also we need to check to make sure the chain ends up where we started or it isn’t valid for the problem; this means that we need to make sure we don’t get stuck in an infinite loop where the chain starts over and we miss it. Solution is written using a simple sum of divisors function that simply brute forces the sum instead of a more elaborate prime factor function; I don’t think the prime factor version would be too much faster because the magnitude of the numbers (under one million) just isn’t enough to warrant such an effort.
Solution written in mono/c# with a helping hand from the linq name-space (mainly for list.min and list.max functions without having to write my own) runs in about 6 seconds on a modern machine. Interestingly enough this could be made parallel if one so desired with a few simple modifications but it runs fast enough already.
using System;
using System.Collections.Generic;
using System.Linq;
namespace Problem95
{
class MainClass
{
public static void Main (string[] args)
{
List<long> chain = new List<long>();
List<long> tmp = new List<long>();
for (long i = 1; i <= 100000; i++)
{
tmp = GenerateChain(i);
if (tmp.Count() > chain.Count())
{
List<long> ch = tmp.Where(x=> x > 1000000).ToList();
if (ch.Count() == 0)
chain = GenerateChain(i);
}
}
Console.WriteLine(chain[0].ToString() + " :: " + chain.Min().ToString());
}
public static List<long> GenerateChain (long num)
{
List<long> chain = new List<long>();
long previous = num;
while (!chain.Contains(previous) && previous < 1000000L)
{
chain.Add(previous);
previous = NextInChain(previous);
}
if (previous != chain[0])
chain.Clear();
if (previous > 1000000L)
chain.Add(9999999L);
return chain;
}
public static long NextInChain (long num)
{
return ProperDivisors(num).Sum();
}
public static List<long> ProperDivisors (long num)
{
long max = (long)Math.Ceiling(Math.Sqrt((double)num));
List<long> RetValue = new List<long>();
RetValue.Add(1L);
if (num % max == 0d)
RetValue.Add(max);
for(long i = 2; i < max; i++)
{
if (num % i == 0L)
{
RetValue.Add(i);
RetValue.Add(num/i);
}
}
return RetValue.Distinct().ToList();
}
}
}