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
<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
NetRexx
Portions translation of Perl 6 <lang NetRexx>/* NetRexx */ options replace format comments java crossref symbols nobinary numeric digits 40
runSample(arg) return
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method summing(maxLimit = 1000) public static
mult = 0
loop mv = 0 while mv < maxLimit
if mv // 3 = 0 | mv // 5 = 0 then
mult = mult + mv
end mv
return mult
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -- translation of perl 6 method sum_mults(first, limit) public static
last = limit - 1 last = last - last // first sum = (last / first) * (first + last) / 2 return sum
method sum35(maxLimit) public static binary
return sum_mults(3, maxLimit) + sum_mults(5, maxLimit) - sum_mults(15, maxLimit)
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method runSample(arg) private static
offset = 30 incr = 10
tmax = 10000000 say tmax.format.right(offset) timing = System.nanoTime mm = 1 loop while mm < tmax say mm.right(offset) summing(mm) mm = mm * incr end timing = System.nanoTime - timing say 'Elapsed time:' Rexx(timing * 1e-9).format(4, 6)'s' say
tmax = 1e+20 say tmax.format.right(offset) timing = System.nanoTime mm = 1 loop while mm < 1e+20 say mm.right(offset) sum35(mm) mm = mm * incr end timing = System.nanoTime - timing say 'Elapsed time:' Rexx(timing * 1e-9).format(4, 6)'s' say return
</lang>
- Output:
10000000
1 0
10 23
100 2318
1000 233168
10000 23331668
100000 2333316668
1000000 233333166668
Elapsed time: 7.853289s
100000000000000000000
1 0
10 23
100 2318
1000 233168
10000 23331668
100000 2333316668
1000000 233333166668
10000000 23333331666668
100000000 2333333316666668
1000000000 233333333166666668
10000000000 23333333331666666668
100000000000 2333333333316666666668
1000000000000 233333333333166666666668
10000000000000 23333333333331666666666668
100000000000000 2333333333333316666666666668
1000000000000000 233333333333333166666666666668
10000000000000000 23333333333333331666666666666668
100000000000000000 2333333333333333316666666666666668
1000000000000000000 233333333333333333166666666666666668
10000000000000000000 23333333333333333331666666666666666668
Elapsed time: 0.002459s
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]
- 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))
- 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