Project Euler 1 - Multiples of 3 and 5 by Loki

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

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

StackExchange Code Review Q#162303, answer score: 9