8
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ What means "by loki"? \$\endgroup\$
    – user120313
    May 3, 2017 at 5:58
  • \$\begingroup\$ @java-devel by "Me". My name is Loki. \$\endgroup\$ May 3, 2017 at 16:54
  • \$\begingroup\$ Why do you place your name in the title? \$\endgroup\$
    – user120313
    May 3, 2017 at 16:55
  • 1
    \$\begingroup\$ @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/… \$\endgroup\$ May 3, 2017 at 17:00

3 Answers 3

9
\$\begingroup\$

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))
\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$ May 2, 2017 at 16:16
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – janos
    May 2, 2017 at 17:29
  • \$\begingroup\$ Now that I agree with (assuming you don't include development time (Just joking)). \$\endgroup\$ May 2, 2017 at 17:46
  • 1
    \$\begingroup\$ Sometimes I wonder how damaged we are doing stuff like this in bash... :-) \$\endgroup\$
    – holroy
    May 2, 2017 at 18:16
3
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Almost every your post has a programming-related abbreviation of some principle (YAGNIA, KISS etc.). Seems you are really collecting them, aren't you? \$\endgroup\$
    – pgs
    May 2, 2017 at 12:58
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ May 2, 2017 at 16:13
  • \$\begingroup\$ 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 \$\endgroup\$ May 2, 2017 at 19:45
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ May 2, 2017 at 23:15
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.