Bash - Sum of all the multiples of 3 or 5 below N

I'm trying to calculate the sum of all the multiples of 3 or 5 below N in bash but my attempts fail at the speed benchmark.

The input format is described as follow:

The first line is T, which denotes the number of test cases, followed by T lines, each containing a value of N.
Sample input:
2
10
100
Expected output:
23
2318

Here are my attemps:

With bc:

#!/bin/bash

readarray input

printf 'n=%d-1; x=n/3; y=n/5; z=n/15; (1 x)*x/2*3   (1 y)*y/2*5 - (1 z)*z/2*15\n' "${input[@]:1}" |
bc

With pure bash:

#!/bin/bash

read t
while (( t-- ))
do
    read n
    echo "$(( --n, x=n/3, y=n/5, z=n/15, (1 x)*x/2*3   (1 y)*y/2*5 - (1 z)*z/2*15 ))"
done

^{remark: I'm using t because the input doesn't end with a newline...}

Both solutions are evaluated as "too slow", but I really don't know what could be further improved. Do you have an idea?

CodePudding user response：

Let's start from the basics and try to optimize it as much as possible:

#!/usr/bin/env bash
read N
sum=0
for ((i=1;i<N;  i)); do
  if ((i%3 == 0 )) || (( i%5 == 0 )); then
      (( sum  = i ))
  fi
done
echo $sum

In the above, we run the loop N times, perform minimally N comparisons and maximally 2N sums (i and sum). We could speed this up by doing multiple loops with steps of 3 and 5, however, we have to take care of double counting:

#!/usr/bin/env bash
read N
sum=0
for ((i=N-N%3;i>=3;i-=3)); do sum =i; done
for ((i=N-N%5;i>=5;i-=5)); do (( i%3 == 0 )) && continue; sum =i; done
echo $sum

In total, we have now maximally 2N/3 2N/5 = 16N/15 sums and N/5 comparisons. This is already much faster. We could still optimzise it by adding an extra loop with a step of 3*5 to subtract the double counting.

#!/usr/bin/env bash
read N
sum=0
for ((i=N-N%3 ; i>=3 ; i-=3 )); do ((sum =i)); done
for ((i=N-N%5 ; i>=5 ; i-=5 )); do ((sum =i)); done
for ((i=N-N; i>=15; i-=15)); do ((sum-=i)); done
echo $sum

This brings us to maximally 2(N/3 N/5 N/15) = 17N/15 additions and zero comparisons. This is optimal, however, we still have a call to an arithmetic expression per cycle. This we could absorb into the for-loop:

#!/usr/bin/env bash
read N
sum=0
for ((i=N-N%3 ; i>=3 ; sum =i, i-=3 )); do :; done
for ((i=N-N%5 ; i>=5 ; sum =i, i-=5 )); do :; done
for ((i=N-N; i>=15; sum-=i, i-=15)); do :; done
echo $sum

Finally, the easiest would just be to use the formula of the Arithmetic Series and write

#!/usr/bin/env bash
read N
(( sum = ( (3   N-N%3) * (N/3)   (5   N-N%5) * (N/5) - (15   N-N) * (N/15) ) / 2 ))
echo $sum

CodePudding user response：

For a pure bash approach,

#!/bin/bash

DBG=1

echo -e "This will generate the series sum for multiples of each of 3 and 5 ..."
echo -e "\nEnter the number of summation sets to be generated => \c"
read sets

for (( k=1 ; k<=${sets} ; k  ))
do
    echo -e "\n============================================================"
    echo -e "Enter the maximum value of a multiple => \c"
    read max
    echo ""

    for multiplier in 3 5
    do
        sum=0
        iter=$((max/${multiplier}))
        for (( i=1 ; i<=${iter} ; i   ))
        do
            next=$((${i}*${multiplier}))
            sum=$((sum =${next}))
            test ${DBG} -eq 1 && echo -e "\t ${next}   ${sum}"
        done
        echo -e "TOTAL:  ${sum}  for ${iter} multiples of ${multiplier} <= ${max}\n"
    done
done

The session log when DBG=1:

This will generate the series sum for multiples of each of 3 and 5 ...

Enter the number of summation sets to be generated => 2

============================================================
Enter the maximum value of a multiple => 15

     3   3
     6   9
     9   18
     12   30
     15   45
TOTAL:  45  for 5 multiples of 3 <= 15

     5   5
     10   15
     15   30
TOTAL:  30  for 3 multiples of 5 <= 15


============================================================
Enter the maximum value of a multiple => 12

     3   3
     6   9
     9   18
     12   30
TOTAL:  30  for 4 multiples of 3 <= 12

     5   5
     10   15
TOTAL:  15  for 2 multiples of 5 <= 12

CodePudding user response：

What about something like this

#! /bin/bash

s35() {
    m=$(($1-1)); echo $(seq -s  3 3 $m) $(seq -s  5 5 $m) 0 | bc   
}

read t
while read n
do
    s35 $n
done

s35() {
    m=$(($1-1)); 
    { sort -nu <(seq 3 3 $m) <(seq 5 5 $m) | tr '\n'  ; echo 0; } | bc   
}

to remove duplicates.

CodePudding user response：

With awk:

BEGIN {
  split("0 0 3 3 8 14 14 14 23 33 33 45 45 45", sums)
  split("0 0 1 1 2 3 3 3 4 5 5 6 6 6", ns)
}
NR > 1 {
  fizzbuzz_sum($0 - 1)
}
function fizzbuzz_sum(x, q, r) {
  q = int(x / 15)
  r = x % 15
  print q*60   q*(q-1)/2*105   sums[r]   (x-r)*ns[r]
}

It's pretty fast on my old laptop that has an AMD A9-9410 processor

$ time seq 0 1000000 | awk -f fbsum.awk >/dev/null

real    0m1.532s
user    0m1.542s
sys     0m0.010s
$

CodePudding user response：

While awk will always be faster than shell, with bash you can use ((m % 3 == 0)) || ((m % 5 == 0)) to identify the multiples of 3 and 5 less than n. You will have to see if it passes the time constraints, but it should be relatively quick,

#!/bin/bash

declare -i t n sum        ## handle t, n and sum as integer values

read t || exit 1          ## read t or handle error

while ((t--)); do         ## loop t times
  sum=0                   ## initialize sum zero
  read n || exit 1        ## read n or handle error
  ## loop from 3 to < n
  for ((m = 3; m < n; m  )); do
    ## m is multiple of 3 or multiple of 5
    ((m % 3 == 0)) || ((m % 5 == 0)) && {
      sum=$((sum   m))    ## add m to sum
    }
  done
  echo $sum               ## output sum
done

Example Use/Output

With the script in mod35sum.sh and your data in dat/mod35sum.txt you would have:

$ bash sum35mod.sh < dat/sum35mod.txt
23
2318