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

• user120313: What means "by loki"?
• Loki Astari: @java-devel by "Me". My name is Loki.
• user120313: Why do you place your name in the title?
• Loki Astari: @java-devel Because the title has to be unique. There are several Project Euler questions with basically the same title. I added my name to make sure it was unique. codereview.stackexchange.com/…

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

• Loki Astari: I disagree that's the best solution (because of the small range); as it probably took much longer to figure out than my one liner which I typed without looking up anything.
• janos: @LokiAstari I didn't mean to write "best" (that really depends on "in terms of what?"). I corrected now to most performant, thanks for pointing out.
• Loki Astari: Now that I agree with (assuming you don't include development time (Just joking)).
• holroy: Sometimes I wonder how damaged we are doing stuff like this in bash... :-)

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.

• pgs: Almost every your post has a programming-related abbreviation of some principle (YAGNIA, KISS etc.). Seems you are really collecting them, aren't you?
• Loki Astari: If the sequence gets too long then xargs correctly breaks over multiple statements. This does result in multiple values but you can solve this by modifying slightly (orig statement above) | tr ' ' '+' | bc as an additional suffix.
• Loki Astari: This blows the command line buffer and still works. ((export end=99999; seq 0 3 ${end}; seq 0 5 ${end}; seq 0 -15 -${end};) | xargs | tr ' ' '+' | bc) | xargs | tr ' ' '+' | bc
• 200_success: The POSIX-mandated minimum for command line lengths is 4096. The numbers for Project Euler 1 should fit within that limit, though it gets uncomfortably close. As an alternative to xargs, I would use awk, but ... | sort -u | paste -sd+ - | bc might be even better.

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