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!
