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)
python_euler20

Full run: 100! and sum of all digits including 0s

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      |
+-----+-----------+---------------+--------------------+
no print fact(99)

Some runs are better than others…

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!

Annunci

Informazioni su Man from Mars

https://extendedreality.wordpress.com/

Un Commento

  1. Pingback: Visto nel Web – 270 | Ok, panico

Dimmi che ne pensi o fai "Ciao ciao!" con la manina // Share your thoughts or just say "Hello!"

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: