Project Euler 1 - Multiples of 3 and 5 by Loki

Question

Multiples of 3 and 5

Multiples of 3 and 5
Problem 1

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.

Used the command line (bash):

(seq 0 3 999; seq 0 5 999) | sort | uniq | xargs | tr ' ' '+' | bc

For the range it seemed good enough:

> time (seq 0 3 999; seq 0 5 999) | sort | uniq | xargs | tr ' ' '+' | bc
233168

real    0m0.021s
user    0m0.019s
sys     0m0.019s

Answer 1

You can replace sort | uniq with sort -u. Note that (...) executes in a sub-shell. Grouping with { ...; } would be more efficient, and equivalent to what you did.

So without optimizing much, keeping it still simple and easy to type, you get:

{ seq 0 3 999; seq 0 5 999; } | sort -u | xargs | tr ' ' '+' | bc

Even so, sorting doesn't sound great. Probably it would be better to not sort, but add the sum of seq 0 -15 -999.

seq is not portable. And it's an additional process. You could either use {start..end..step} native Bash syntax, or native Bash counting for loops, but I bet you intentionally didn't because it's a bit longer to type.

And as Bash can easily do such simple math, you don't really need bc.

Here's a more efficient version, using fewer processes:

((x = $({ seq 0 3 999; seq 0 5 999; } | tr '\n' '+')$(seq 0 -15 -999))); echo $x

Here's another version using native Bash features only:

x=0
for ((i = 0; i < 1000; i += 3)); do ((x += i)); done
for ((i = 0; i < 1000; i += 5)); do ((x += i)); done
for ((i = 0; i < 1000; i += 15)); do ((x -= i)); done
echo $x

The most performant solution is of course using the closed form formula:

n=999; echo $((3 * (n / 3) * (n / 3 + 1) / 2 + 5 * (n / 5) * (n / 5 + 1) / 2 - 15 * (n / 15) * (n / 15 + 1) / 2))

Answer 2

A rather interesting choice of language for solving the Project Euler problem. Are you going to do the rest of the problems in bash, as well?

The common pitfall of this particular Euler problem is the inclusion of the 15's as they are divided by both 3 and 5. By adding the uniq after the sort you avoid that pitfall.

Nice usage of tr and bc to calculate the sum, however be aware that if you increase the sequences enough you might run into issues related to argument lengths. If you do so, then xargs might also start acting funny. (Update: As seen in comments, this can be counteracted by introducing a secondary level of xargs, tr and bc)

That leaves not that much to comment upon, besides that this is unix, so there is a ton of ways to do this. Including various options with sed, awk, perl, bash scripting, and so on... This is however, a nice, neat and easy solution which fits the extended YAGNIA principle perfect. That is: You Ain't Gonna Need It Again.

Answer 3

As I said in the (now deleted) comment, I don't think that is really a "bash" solution.

In pure bash you can do something like this, looping once:

#!/bin/bash

COUNTER=0
TOTALSUM=0
A=0
while [  $COUNTER -lt 1000 ]; do
    let A=COUNTER%5
    if [[ $A = 0 ]]; then
        let TOTALSUM=TOTALSUM+COUNTER
    else
        let A=COUNTER%3
        if [[ $A = 0 ]]; then
            let TOTALSUM=TOTALSUM+COUNTER
        fi
    fi
    let COUNTER=COUNTER+1 
done

echo $TOTALSUM

But if you want the "one-liner" version (which is not really one line after all):

for ((i = 0; i < 1000; i += 1)); do let A=i%5; let B=i%3; if [[ $A = 0 || $B = 0 ]]; then let TOTALSUM=TOTALSUM+i; fi; done; echo $TOTALSUM