Duncan's blog

November 11, 2008

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.

4 Comments »

  1. Hi Duncan

    Project Euler looks like fun!

    I copied your code into the VBA editor in Excel, changed a few things to make it work in VB, and it gives the right answer in less than 1 second🙂

    Comment by dougaj4 — November 12, 2008 @ 9:37 am | Reply

  2. That’s reassuring! There were further amendments I could have made to the code to make the whole thing even faster, but decided to leave it as it was. I think just changing the loop from x/2 to the square root of x made the big difference.

    Comment by duncancumming — November 12, 2008 @ 7:54 pm | Reply

    • you got it

      Comment by jagadeeshwaran — April 21, 2011 @ 2:58 pm | Reply

  3. […] previously blogged about this Project Euler puzzle nearly 6 years ago, using ColdFusion.  This is my approach using PHP as a simple practical exercise for myself, and […]

    Pingback by Project Euler: problem 21 (PHP) | Duncan's blog — October 4, 2014 @ 8:03 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: