Duncan's blog

February 2, 2009

Project Euler problem 34

Filed under: Coldfusion,Project Euler — duncan @ 12:00 am
Tags: , , , , ,

Problem 34:

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

This one doesn’t seem too hard. However, the tricky part is determining what the upper bound should be. I wasn’t really sure how this one would progress, so decided to set a relatively low upper bound, 99999. I was then going to check what sort of values I was getting back, then increase the bound as necessary.

However running the following code, I saw there weren’t very many values at all. Just on the off-chance I’d got the final solution, I entered it into the Project Euler page, and I had indeed got it right, purely by luck.

I later discovered that the real upper bound that you would theoretically need to use is 9999999. Doing that with the following code would take much longer.

<cfscript>
function factorial(x)
{
	var i = 0; 
	var factorial = 1;
	
	for (i = x; i GT 1; i = i - 1)
	{
		factorial = factorial * i;
	}
	
	return factorial;
}
</cfscript>

<cfset numbers = ArrayNew(1)>
<cfset total = 0>

<!--- how far do we need to loop?  Let's just start and see how it progresses... --->
<cfloop index="i" from="3" to="99999">
	<cfset sum = 0>
	
	<!--- get the factorial of each digit of i --->
	<cfloop index="j" from="1" to="#Len(i)#">
		<cfset sum = sum + factorial(Mid(i, j, 1))>
	</cfloop>
	
	<!--- does i = the sum of the factorials? --->
	<cfif i EQ sum>
		<cfset ArrayAppend(numbers, i)>
	</cfif>
</cfloop>

<cfdump var="#numbers#">

<cfloop index="i" from="1" to="#ArrayLen(numbers)#">
	<cfset total = total + numbers[i]>
</cfloop>

<cfoutput>#total#</cfoutput>

Factorials can get very large quickly. Fortunately I’m only ever going to be putting values from 0 to 9 into my factorial function.

Note that 0! = 1, not zero. This is the empty product. Fortunately my factorial function takes care of that.

Then I loop, ignoring 1 and 2, to my lucky choice of 99999 for the upper limit (the comment in my code gives an idea of how I was thinking!). Sum up the factorial of each digit. Check if that sum is the same as our number; if so add it to an array.

At the end I dumped out the array, just to see what sort of results I was getting. Then later I added in the final loop, adding up the values of the array to give the correct solution.

Judging by the forum discussion, there wasn’t any clear idea of what the upper limit should be, with most people seeming to take an educated guess.

Spoiler alert:
Interestingly, there are only four numbers that this works for, and they’re known as factorions. Two of those are 1 and 2, so the solution to this puzzle only requires you to work out two other numbers. And one of them, 145, has already been given to you in the problem!

3 Comments »

  1. I got stuck on this because I hadn’t been calculating 0! => 1

    also, for the end of the range, you’d want 2540160 (which is 7*9!) as that is the greatest number 7 digits could add to. 8 digits would not result in an 8 digit number even with 99999999

    you can also speed it all up a lot by pre-calculating 0! to 9! and stuffing them in an array to reference

    Comment by juhanic — December 5, 2010 @ 12:44 pm | Reply

  2. I like your idea of preloading all the factorials – I put them into a structure, and it more than halved the execution time.

    Comment by duncan — December 5, 2010 @ 1:11 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 34 (PHP) | Duncan's blog — October 10, 2014 @ 8:02 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

Blog at WordPress.com.

%d bloggers like this: