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\$
  • \$\begingroup\$ What means "by loki"? \$\endgroup\$ – java-devel May 3 '17 at 5:58
  • \$\begingroup\$ @java-devel by "Me". My name is Loki. \$\endgroup\$ – Martin York May 3 '17 at 16:54
  • \$\begingroup\$ Why do you place your name in the title? \$\endgroup\$ – java-devel May 3 '17 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\$ – Martin York May 3 '17 at 17:00
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\$
  • \$\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\$ – Martin York May 2 '17 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 '17 at 17:29
  • \$\begingroup\$ Now that I agree with (assuming you don't include development time (Just joking)). \$\endgroup\$ – Martin York May 2 '17 at 17:46
  • 1
    \$\begingroup\$ Sometimes I wonder how damaged we are doing stuff like this in bash... :-) \$\endgroup\$ – holroy May 2 '17 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\$
  • \$\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 '17 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\$ – Martin York May 2 '17 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\$ – Martin York May 2 '17 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\$ – 200_success May 2 '17 at 23:15
0
\$\begingroup\$

I imagine it would be a good solution to loop through the numbers twice, once only looking at numbers divisible by 3 and once looking at only numbers divisible 5.

In pseudo code:

sum = 0;

for(counter = 3; counter < 1000; counter += 3)
    if(counter % 5 != 0)
        sum += counter

for(counter = 5; counter < 1000; counter += 5)
    if(counter % 3 != 0)
        sum += counter

This way you don't have to loop over all 1000 numbers.

\$\endgroup\$
  • 2
    \$\begingroup\$ Please explain how you might reasonably accomplish that in Bash. \$\endgroup\$ – 200_success May 2 '17 at 23:16
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, privacy policy and cookie policy

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