# Project Euler: problem 20

Sometimes there is just no clever trick, no obscure theorem, no alternative method one can use to solve a problem: this is the case for problem 20 from Project Euler’s collection, that is only a matter of crunching numbers in the only possible way.

n! means n × (n − 1) × … × 3 × 2 × 1

For example, 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

Given the magnitude of $N=100!$ and the specific goal, `bash` is of course out of the game, unless you calculate it beforehand and feed it as a string into a script that will sum its digits; I will do that eventually, but it can’t be the first solution. I’ll have to resort instead to the few rough things I still remember about Python. Still, I left myself some room to play and “optimize” the code. Yes, because there is still some unneeded excess to shave off, in the form of a streak of ending “0”s. All these ending “0” are of course a waste of time when computing the final sum of digits and must be skipped somehow. Let’s see how many of them are there.

First, every multiplication np * n5 (n5 being a number ending with 5 and p the last digit being even) yields to a number ending with 0. From 1 to 100 and pairing numbers in the same tens (2 * 5 or 14 * 15 or 76 * 75, for example), there are 10 pairs to consider (of course you can count a single pair every 10 numbers), hence 10 ending 0s.

Additionally, each of the 9 “round” numbers n0 (10, 20, …, 90) adds a final 0. One extra 0 is given by the pair  20 * 50 = 1000, for total 10 more ending 0s. Finally, I could count 100 for 2 more ending 0s unless…

Another way to spare a few CPU cycles would be to actually compute $N'=99!$ instead of $N$, since the last multiplication by would only add 2 more 0s. So, the last 20 digits of $N'$ can be safely skipped.

The code below runs the “full” calculation ( $N$, sum of all digits including 0s), accounting for all the considerations above within comments:

```import math
import time
start=time.clock()
nfact = math.factorial(100)
''' or math.factorial(99) because 100 just adds 2 ending "0" '''
nlen = len(str(nfact))
nsum = 0
for i in range(0, nlen):
''' (0, nlen-20) for 99! / (0, nlen-22) for 100! '''
nsum = nsum + int(str(nfact)[i])

print(nsum)
'''print(nlen) / print(nfact) if you wish'''
print(time.clock()-start)
```

Finally, the answer is 648 and mr. Euler is happy!

I have run the script repeatedly to test the different combinations of internal parameters but, as I was expecting, there are very few differences in execution times.

Here a short summary of (average) results:

```+-----+-----------+---------------+--------------------+
| n!  | compute   | sum of digits | sum of digits      |
|     | factorial | including 0s  | excl. 20 ending 0s |
+-----+-----------+---------------+--------------------+
| 99  |  8*10-6 s |   4.2*10-4 s   |      4*10-4 s      |
+-----+-----------+---------------+--------------------+
| 100 |  8*10-6 s |   4.7*10-4 s   |      4*10-4 s      |
+-----+-----------+---------------+--------------------+```

Adding the 156 (for 99!) or 158 (for 100!) digits takes the largest part of computational time, of course, since there is a double conversion of the whole number into a string, to extract the i-th digit and of the extracted digit back to integer. But that’s the way Python runs, as far as my knowledge goes!

## Teaching an old dog new tricks: bash and bc to the rescue

When it comes to real maths, `bc` is the usual tool that pairs with `bash` to handle that. We are dealing with a large integer that `bash` can’t compute and do maths with by itself (overflow!), although it can handle it as a string for our purpose. Functions not available in `bc`, such as calculation of factorial, can be defined and loaded when `bc` is run.

So, let’s open the `man` page to understand how to accomplish that, shall we? Oh… wait… one of the examples is exactly a function to calculate the factorial!

Lesson learned: always – alwaysRead The F****ing Manual!

Having solved the hardest step, I didn’t even bother to write a script: instead, I went straight on the command line. So, let’s list steps in order:

1. create a “library” `bc` will load (“`-l`” option), containing the factorial functional: that meant creating a file (`fact.bc`) where I pasted the function as found in the `man` page.
2. compute the factorial, clean up the output of `bc` (long numbers are printed to `stdout` with “\” line breaks) and store the value in a variable for later use:
`nfact=\$(echo "f(100)" | bc -l fact.bc | tr -d '\n\\')`
3. purge all 0s from the number: that’s pretty cool because also 0s in the middle are removed
`nfact=\${nfact//0/}`

I used `bash` string manipulation built-in (and that’s cool!) although, on a second thought, `tr` could do the whole job (`tr -d '0\n\\'`); too late, the screenshot was already taken!

4. loop on each of the remaining digits to calculate and print out the sum (variable `\$ds`): one-liner, C-style loop, parameter length and substring extraction. That’s about one million `bash` karma points, isn’t it?
5. profit(?) So, maybe the shell was not as fast as Python for the task (and no, I didn’t even set up the nanoseconds trick to measure execution time), but the fun was worth every millisecond of it! See you on next problem, mr. Euler!

## 1 Comment

I commenti sono chiusi.