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 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 instead of , since the last multiplication by would only add 2 more 0s. So, the last 20 digits of can be safely skipped.

The code below runs the “full” calculation (, 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 – **always** – *Read 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:

- 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. - 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\\')

- purge
**all**0s from the number: that’s pretty cool because also 0s in the middle are removednfact=${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! - 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? - 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.