Sum multiples of 3 and 5

Sum multiples of 3 and 5
You are encouraged to solve this task according to the task description, using any language you may know.

The objective is to write a function that finds the sum of all positive multiples of 3 or 5 below n. Show output for n = 1000.

Extra credit: do this efficiently for n = 1e20 or higher.

BASIC

Works with: FreeBASIC

<lang basic>Declare function mulsum35(n as integer) as integer Function mulsum35(n as integer) as integer

   Dim s as integer
   For i as integer = 1 to n - 1
       If (i mod 3 = 0) or (i mod 5 = 0) then
           s += i
       End if
   Next i
   Return s

End Function Print mulsum35(1000) Sleep End</lang>

Output:

233168

D

<lang d>import std.stdio, std.range, std.algorithm;

long sum35(in long n) {

   return n.iota.filter!q{ a % 3 == 0 || a % 5 == 0 }.reduce!q{a + b};

}

void main() {

   1000.sum35.writeln;

}</lang>

Output:

233168

Perl 6

<lang perl6>sub sum35($n) { [+] grep * %% (3|5), ^$n; }

say sum35 1000;</lang>

Output:

233168

Here's an analytical approach that scales much better for large values. <lang perl6>sub sum-mults($first, $limit) {

   (my $last = $limit - 1) -= $last % $first;
   ($last div $first) * ($first + $last) div 2;

}

sub sum35(\n) {

   sum-mults(3,n) + sum-mults(5,n) - sum-mults(15,n);

}

say sum35($_) for 1,10,100...10**30;</lang>

Output:

0
23
2318
233168
23331668
2333316668
233333166668
23333331666668
2333333316666668
233333333166666668
23333333331666666668
2333333333316666666668
233333333333166666666668
23333333333331666666666668
2333333333333316666666666668
233333333333333166666666666668
23333333333333331666666666666668
2333333333333333316666666666666668
233333333333333333166666666666666668
23333333333333333331666666666666666668
2333333333333333333316666666666666666668
233333333333333333333166666666666666666668
23333333333333333333331666666666666666666668
2333333333333333333333316666666666666666666668
233333333333333333333333166666666666666666666668
23333333333333333333333331666666666666666666666668
2333333333333333333333333316666666666666666666666668
233333333333333333333333333166666666666666666666666668
23333333333333333333333333331666666666666666666666666668
2333333333333333333333333333316666666666666666666666666668
233333333333333333333333333333166666666666666666666666666668

Python

Three ways of performing the calculation are shown including direct calculation of the value without having to do explicit sums in sum35c() <lang python>def sum35a(n):

   'Direct count'
   # note: ranges go to n-1
   return sum(x for x in range(n) if x%3==0 or x%5==0)

def sum35b(n):

   "Count all the 3's; all the 5's; minus double-counted 3*5's"
   # note: ranges go to n-1
   return sum(range(3, n, 3)) + sum(range(5, n, 5)) - sum(range(15, n, 15))
   

def sum35c(n):

   'Sum the arithmetic progressions: sum3 + sum5 - sum15'
   consts = (3, 5, 15)
   # Note: stop at n-1
   divs = [(n-1) // c for c in consts]
   sums = [d*c*(1+d)/2 for d,c in zip(divs, consts)]
   return sums[0] + sums[1] - sums[2]

1. test

for n in range(1001):

   sa, sb, sc = sum35a(n), sum35b(n), sum35c(n)
   assert sa == sb and sa == sc

print('For n = %7i -> %i\n' % (n, sc))

1. Pretty patterns

for p in range(7):

   print('For n = %7i -> %i' % (10**p, sum35c(10**p)))</lang>

Output:

For n =    1000 -> 233168

For n =       1 -> 0
For n =      10 -> 23
For n =     100 -> 2318
For n =    1000 -> 233168
For n =   10000 -> 23331668
For n =  100000 -> 2333316668
For n = 1000000 -> 233333166668

REXX

<lang rexx>/* REXX ***************************************************************

• 14.05.2013 Walter Pachl
  • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • /

Say mul35() exit mul35: s=0 Do i=1 To 999

 If i//3=0 | i//5=0 Then
   s=s+i
 End

Return s</lang> Output:

233168