Project Euler: problem 21

Problem 21:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a != b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

I passed over this one initially, and came back to it later. It wasn’t too difficult, but I got the wrong answer first time round.

We need to loop up to 9999. For each number (i), work out what its factors are, and add them up (let’s call this sum1). Then work out what the factors of sum1 are, and add them up (sum2). If i equals sum2, then i and sum1 are amicable numbers.

My mistake was forgetting to check that i and sum1 are different. It turns out several numbers seem to be amicable, but are the same. e.g. the factors of 6 are 1, 2 and 3, which add up to 6; but (6, 6) is not an amicable pair.

<cfset d = StructNew()>

<cfscript>
function getFactors(x)
{
	var i = 0; 
	var factors = ArrayNew(1);
	
	for (i = 1; i LTE x/2; i = i + 1)
	{
		if (NOT x MOD i)
		{	// its a factor
			ArrayAppend(factors, i);
		}
	}
	
	return factors;
}

function sumFactors(x)
{
	var i = 0;
	var sum = 0 ;
	
	for (i = 1; i LTE ArrayLen(x); i = i + 1)
	{
		sum = sum + x[i];
	}
	
	return sum;
}
</cfscript>

<cfloop index="i" from="1" to="9999">
	<cfset j = getFactors(i)>	<!--- factors of i --->
	<cfset k = sumFactors(j)>	<!--- sum of those factors --->
	<cfset l = getFactors(k)>	<!--- factors of that sum --->
	<cfset m = sumFactors(l)>	<!--- sum of those factors --->
	
	<cfif m EQ i AND NOT StructKeyExists(d, i) AND NOT StructKeyExists(d, k) AND i NEQ k>
	<!--- amicable pair --->
		<cfset d[i] = k>
		<cfset d[k] = m>
	</cfif>
</cfloop>

<cfset sum = 0>
<cfset d2 = StructKeyArray(d)>

<cfloop index="i" from="1" to="#ArrayLen(d2)#">
	<cfset sum = sum + d[d2[i]]>
</cfloop>

<cfoutput>#sum#</cfoutput>

This code is pretty slow, taking about eight minutes to run. The PDF available after you complete it has a more optimised version. After doing a minor rewrite based on that, it only took 15 seconds! So ignore the code above, take a look at this instead:

<cfscript>
function sumFactors(x)
{
	var i = 0; 
	var sum = 1;
	
	for (i = 2; i LTE SQR(x); i = i + 1)
	{
		if (NOT x MOD i)
		{	// its a factor
			sum = sum + i;
			if (i NEQ (x / i))
				sum = sum + (x / i);
		}
	}
	
	return sum;
}
</cfscript>

<cfset sum = 0>

<cfloop index="i" from="1" to="9999">
	<cfset j = sumFactors(i)>	<!--- sum factors of i --->
	<cfset k = sumFactors(j)>	<!--- sum of those factors --->
	
	<cfif i EQ k AND j NEQ k>
	<!--- amicable pair --->
		<cfset sum = sum + j>
	</cfif>
</cfloop>

<cfoutput>#sum#</cfoutput>

So what’s the difference? Firstly, I was using a Struct to store each amicable pair. I did away with that, and just added directly to my total. I wouldn’t normally code like that; for these sort of things its good to have a variable that you can then interrogate later to see actually what numbers are we calling amicable. However, on the assumption that the code is now correct, doing away with it removes one level of complexity. I can then remove one StructNew function call, the two StructKeyExists function calls, one StructKeyArray function call, and one cfloop.

Secondly, instead of having one function to get all the factors, and another function to then add those together, I simplified this to just one function that both finds the factors and adds them together.

This function originally extended to half of x, e.g. if the number was 198, the largest factor of that is 99. However the function rewritten only extends to the square root of x, and adds both the factor and x / factor. e.g. for 220 we only go as far as 14, and add 1 (outwith our loop), 2 and 110 (220/2), 4 and 55 (220/4), 5 and 44 (220/5), 10 and 22 (220/10), 11 and 20 (220/11).

Then we sum those factors (sum1), then find the factors of sum1, sum them (sum2) and compare i and sum2. Assuming they match and sum1 and sum2 are different, we add sum1 to our total.