Project Euler and bash: maths for fun!

This article has been originally published in Italian (here). Feedbacks on content and translation are appreciated. Contributions are welcome. The original article must be considered the reference in case of updates.

Some time ago I’ve come across Project Euler, a collection of maths problems (ranging from easy to “WTF is this stuff!?!“) to be solved putting together some code. I promptly used the few bash tricks I’ve learned to tackle the first problems the best I could: although my “best” might not be so much, I can proudly state that I’ve been able to write down the simple solution scripts almost at the first try.

I have decided to use the problems listed in Project Euler’s pages to restart practising (learning, actually!) shell scripting, at least solving those I can understand! So, here you are the first, quite easy, challenge from the list. Enjoy!


Problem 1 [link]

Multiples of 3 and 5: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

#!/bin/bash
sum=0
printf "%4s\t%8s\n" "Num" "Sum"
for i in {1..999}
do
if [[ $((i%3)) -eq 0 ]] || [[ $((i%5)) -eq 0 ]]
then sum=$((sum+i))
# One line for each found number and sum progress
printf "%4s\t%8s\n" $i $sum
# Single line, overwritten at each found number
#printf "\r%4s\t%8s" $i $sum
# Makes sense in combination with
# single line output to show progress
#sleep 0.02
fi
done
#echo $sum #final result
exit

Output:

 Num         Sum
   3           3
   5           8
   6          14
[...]      [...]
 996      232169
 999      233168

Et voilà, the requested result, 233168, summing 466 numbers (999/3=333 multiples of 3 and 999/5=199 multiples of 5, minus 999/15=66 that are multiples of both) that comply with the problem statement; also wc confirms (the first counted line is the list title).

$ ./euler1.sh | wc -l
467

Provided the code is working, I devised different “scenarios” combining the commented lines to measure the change in script execution times:

                        sleep | 0,02s |   no  | 
+------------+----------------+-------+-------+
| Execution  |  Only result   |   -   |  0,01 |
|            +----------------+-------+-------|
| time       |   Single line  | 10,19 |  0,02 |
|            +----------------+-------+-------|
| (seconds)  |    Multiline   | 10,25 |  0,03 |
+------------+----------------+-------+-------+

Execution time – only final result

 

Time is (roughly) measured by /usr/bin/time -f %e ./euler1.sh command (“-f %e” is the output format, execution time in seconds).

euler1_type_time

time – builtin

Please note that there is an actual program (see “man time” for further detail), different from the shell “builtin” command time (such as cd and echo): the latter has no options to modify output format.

And, since you surely don’t trust the result in the table above, here are a couple more screenshots!

Execution time – single line, no pause

 

Doing the maths, I’ve noticed a small quirk: the difference between execution time in “single line” case, with and without pause, is about 10,17s (10,19 – 0,02) due to instruction sleep 0.02. The figures don’t add up, though, since 466 pauses lasting 0,02s would make 9,32s: the remaining 0,85s are therefore an hint to the time needed to process the same 466 instructions. One more easy calculation suggests then that 0,85s/466=0,0018240343s are needed for the whole system to “acquire” the instruction, before actually executing it.

Execution time – single line, pause 0,02s

 

If pictures are still not enough, please welcome a good old animated GIF (it seems they’re all the rage, again)!

script_run

As always I have wandered of a bit, as always I have peeked in hardware and in the Penguin inside it, as always I had some fun with stuff that most people look at suspiciously and from afar, to say the least: I’ll go on this way.

Informazioni su Man from Mars

https://extendedreality.wordpress.com/

  1. Jakob

    Hm… the task is “Find the sum […] *below* 1000.”. So it must be `for i in {1..999}`, right?

    Mi piace

    • DAMN!!! You’re absolutely right! I fixed the mess.
      I started the script with a “while [[ $i -lt 1000 ]]” that would actually stop at 999 (so, *below* 1000), but then I changed my mind and switched to the “for” statement, that I prefer for defined value sets.
      The “1000” got stuck, though…
      Lessons learned:
      1) No matter how simple the code is, there will always be bugs and mistakes!
      2) Coding late at night is not good
      3) Don’t drink and code

      Mi piace

  2. Pingback: Project Euler – Problem 2 | Extended Reality

  3. Ralph Magpie

    Egregio Prof.,
    ” vengo con questa mia addirvi unaparola” che la lettura del suo ultimo articolo su questi quesiti sfiziuselli di matematica, mi ha suscitato la curiosità di provare.. ed ho provato!
    Volevo segnalarle una imprecisione e comunicarle che a mio avviso prima della forza bruta esiste la via analitica.
    La prima segnalazione è che i numeri modulo 5 sono 199 e non 200 (il 1000 è escluso).
    Per valutare se è più veloce l’analitico o il bruteforce le allego un programmino (in Python naturalmente) per la valutazione dei tempi
    ————————

    import time
    
    def timeit(method):
        def timed(*args, **kw):
            ts = time.time()
            result = method(*args, **kw)
            te = time.time()
            print('[%s] exec time: %f sec'%(method.__name__,(te-ts)))
            return result
        return timed
    
    @timeit
    def analitics():
        def f(end, k):
            sup = int((end-1)/k)
            return k*sup*(sup+1)/2
        return int(f(1000,3)+f(1000,5)-f(1000,15))
    
    @timeit
    def bruteforce():
        return sum([i for i in range(1,1000) if i%3==0 or i%5==0])
    
    print(analitics())
    print(bruteforce())
    

    ———————–
    In questo caso non si riesce ad apprezzare la differenza, ma se al posto di 1000 scrive 10000 o 100000 la cosa cambia.
    A risentirla al più presto e non è escluso che le soluzioni agli altri problemi si possano leggere sul mio blog (ebbene si a volte ritornano) dal nome pachialone….
    Cordiali saluti

    Mi piace

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: