THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  SumFactorials().  This function takes an integer as its argument and returns the sum of the factorials of the digits of that integer.  For example, if the argument is 234, the function returns 32 (because 234 --> 2! + 3! + 4! = 2 + 6 + 24 = 32).

This code will only find function with arguments up to a maximum possible value of s. See the table below for the limits.

Type

Exponent of 2
Value

int 230 1073741824
uint 231 2147483648
int64 261 2305843009213693952
uint64 262 4611686018427387904

Declaring the function must be done like this:

declare SumFactorials(s: int).

And here's the code:

sub SumFactorials(s)
' totalises the factorials of each digit
' of argument s then returns their sum
def sum, temp: int
temp = s
sum = 0
do
    ' add factorial of LSD to sum
    sum = sum + Factorial(temp % 10)
    ' chop LSD off temp
    temp = temp/10
until temp = 0: 'all digits chopped off
return sum


Overview:  The output will be stored in variable sum, which is initialised to zero.  A simple DO loop uses variable temp to iterate over the individual digits of the argument.

At each iteration, whatever digit value is derived by temp is passed as parameter to the function Factorial(), which returns the factorial of its argument.  Clearly, then, function Factorial() must be included with your program.  To get a copy, click here now.

When all the digits of argument s have been processed, the sum of all their factorials will be stored in sum, and this is returned to the calling routine.

The following few lines of code do all the work.  I've numbered them to make explanations simpler.

1
2
3
4
5
6
7
8

def sum, temp: int
temp = s
sum = 0
do
    sum = sum + Factorial(temp % 10)
    temp = temp/10
until temp = 0

return sum

Let's look at the above code in detail now.

1

def sum, temp: int.  Creates the local variables to be used in the function. sum holds the sum of the factorials, increasing as each of the argument's digits are processed one at a time.  temp is used to extract the LSD (least significant or right-most digit) of the argument for processing.  More on how it does this later.

2

temp = s.  Copies the value of argument s into local variable temp. This isolates s from the changes that the rest of the code will make to temp.

3

sum = 0.  Variable sum is initialised to zero. It has to be zero, since it will be used to totalise the factorials of the digits of argument s one at a time and cumulatively.

4

do.  Opens the main DO loop. It only contains a couple of lines, but they do all the real work in this function. It relies heavily on integer arithmetic.

5

sum = sum + Factorial(temp % 10).  Let's look at this line from inside the brackets first.  Integer arithmetic is used to isolate the LSD (right-most) digit of temp. The percentage sign means "What would be the remainder if I were to divide temp by 10?"  If temp contained, say, 253, the answer would be 3, because that's the remainder. 

So we can rewrite the last bit of line 5, using our example where temp is 253, as
Factorial(3). As explained above, Factorial() is an external function which you must use with this code.  When called in this way, it will return 6, because 6 is the factorial of 3 (that is, 1 x 2 x 3 = 6).

Now we can rewrite the line for this example in the following way: 
sum = sum + 3. Remember, sum was intialised to zero, so, after processing this line, sum will hold 3.

6

temp = temp/10.  Although part of line 5 asked the question "What would be the remainder if I were to divide temp by 10?" it didn't actually make the division - temp was unchanged by the execution of the line. 

This line actually makes that change - it divides temp by 10. Now, temp was declared as an integer.  So dividing it by 10 will still leave an integer.  That means, any remainder will be discarded.

And Line 7 is thus saying "Divide the contents of variable temp by 10, discard any remainder, and store the result in temp, over-writing whatever value was previously stored in there."

In the case of the example where temp held 253, it will hold 25 after the execution of this line - not 25.3 or 25 remainder 3.


7

until temp = 0.  The code has now reached the end of the DO loop and has to decide what to do next.  Should it re-execute the loop, or quit? It makes this decision by looking at the value of temp

Every time it goes around the loop, it makes temp smaller. That number 253 above would become 25, then 2, then 0. At each stage, it would find the factorial of the LSD and save its value in sum

Eventually, all digits will have been processed and temp becomes zero at this point.  This is the ideal indicator that all digits have been accounted for, and there will be no need to re-execute the loop.

So, this line can be paraphrased as "If the last division of temp by 10 left zero after any remainder was discarded, quit the DO loop, otherwise execute it again."

8

return sum.  At this point, all the digits have been processed and the sum of their factorials accumulated and totalised in variable sum.  All that remains is to return sum to the calling routine, and this line takes care of that.

The best way to understand how the function works is to trace a real example through. Let's take the argument as 5326, which gets stored in variable temp.

The table below shows how each pass of the DO loop changes things. On the first pass it works out that the LSD is 6 and finds its factorial, 720. This is added to sum, making its new value 720. Now temp is reduced to 532 - effectively, the final digit has been chopped off.

The DO loop recognises that temp is still greater than zero, so it runs again.  This time it increases sum to 722 and reduces temp to 53.

A couple more passes and sum is now 848 while temp is zero. The DO loop sees the zero value and quits, allowing the code to move on to the next line of instruction.

temp

5326
532
53
5
0
temp % 10

6
2
3
5
Factorial(temp % 10)

720
2
6
120
sum (old)

0
720
722
728
sum (new)

720
722
728
848
temp/10

532
53
5
0


MAIN MENU
HOW DOES IT WORK?

Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 5th, 2010.