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.
APL
<lang apl>⎕IO←0 {+/((0=3|a)∨0=5|a)/a←⍳⍵} 1000</lang>run
- Output:
233168
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
C++
<lang cpp>
- include <iostream>
//-------------------------------------------------------------------------------------------------- typedef unsigned long long bigInt;
using namespace std; //-------------------------------------------------------------------------------------------------- class m35 { public:
void doIt( bigInt i )
{
bigInt sum = 0; for( bigInt a = 1; a < i; a++ ) if( !( a % 3 ) || !( a % 5 ) ) sum += a;
cout << "Sum is " << sum << " for n = " << i << endl << endl;
}
// this method uses less than half iterations than the first one
void doIt_b( bigInt i )
{
bigInt sum = 0; for( bigInt a = 0; a < 28; a++ ) { if( !( a % 3 ) || !( a % 5 ) ) { sum += a; for( bigInt s = 30; s < i; s += 30 ) if( a + s < i ) sum += ( a + s );
} } cout << "Sum is " << sum << " for n = " << i << endl << endl;
}
}; //-------------------------------------------------------------------------------------------------- int main( int argc, char* argv[] ) {
m35 m; m.doIt( 1000 ); return system( "pause" );
} </lang>
- Output:
Sum is 233168 for n = 1000
COBOL
Using OpenCOBOL.
<lang cobol> Identification division. Program-id. three-five-sum.
Data division. Working-storage section. 01 ws-the-limit pic 9(18) value 1000. 01 ws-the-number pic 9(18). 01 ws-the-sum pic 9(18). 01 ws-sum-out pic z(18).
Procedure division. Main-program.
Perform Do-sum
varying ws-the-number from 1 by 1
until ws-the-number = ws-the-limit.
Move ws-the-sum to ws-sum-out.
Display "Sum = " ws-sum-out.
End-run.
Do-sum.
If function mod(ws-the-number, 3) = zero
or function mod(ws-the-number, 5) = zero
then add ws-the-number to ws-the-sum.
</lang>
Output:
Sum = 233168
Using triangular numbers: <lang cobol> Identification division. Program-id. three-five-sum-fast.
Data division. Working-storage section. 01 ws-num pic 9(18) value 1000000000. 01 ws-n5 pic 9(18). 01 ws-n3 pic 9(18). 01 ws-n15 pic 9(18). 01 ws-sum pic 9(18). 01 ws-out.
02 ws-out-num pic z(18). 02 filler pic x(3) value " = ". 02 ws-out-sum pic z(18).
Procedure division. Main-program.
Perform
call "tri-sum" using ws-num 3 by reference ws-n3
call "tri-sum" using ws-num 5 by reference ws-n5
call "tri-sum" using ws-num 15 by reference ws-n15
end-perform.
Compute ws-sum = ws-n3 + ws-n5 - ws-n15.
Move ws-sum to ws-out-sum.
Move ws-num to ws-out-num.
Display ws-out.
Identification division. Program-id. tri-sum.
Data division. Working-storage section. 01 ws-n1 pic 9(18). 01 ws-n2 pic 9(18).
Linkage section. 77 ls-num pic 9(18). 77 ls-fac pic 9(18). 77 ls-ret pic 9(18).
Procedure division using ls-num, ls-fac, ls-ret.
Compute ws-n1 = (ls-num - 1) / ls-fac. Compute ws-n2 = ws-n1 + 1. Compute ls-ret = ls-fac * ws-n1 * ws-n2 / 2. goback.
</lang>
Output:
1000000000 = 233333333166666668
D
<lang d>import std.stdio, std.bigint;
BigInt sum35(/*in*/ BigInt n) pure /*nothrow*/ {
static BigInt sumMul(/*in*/ BigInt n, in int f) pure /*nothrow*/ {
/*immutable*/ auto n1 = (n - 1) / f;
return f * n1 * (n1 + 1) / 2;
}
return sumMul(n, 3) + sumMul(n, 5) - sumMul(n, 15);
}
void main() {
1000.BigInt.sum35.writeln; (10.BigInt ^^ 20).sum35.writeln;
}</lang>
- Output:
233168 2333333333333333333316666666666666666668
Haskell
Also a method for calculating sum of multiples of any list of numbers.
<lang haskell>import Data.List (nub)
sumMul n f = f * n1 * (n1 + 1) `div` 2 where n1 = (n - 1) `div` f sum35 n = sumMul n 3 + sumMul n 5 - sumMul n 15
-- below are for variable length inputs pairLCM [] = [] pairLCM (x:xs) = map (lcm x) xs ++ pairLCM xs
sumMulS _ [] = 0 sumMulS n s = sum (map (sumMul n) ss) - sumMulS n (pairLCM ss)
where ss = nub s
main = do
print $ sum35 1000 print $ sum35 100000000000000000000000000000000 print $ sumMulS 1000 [3,5] print $ sumMulS 10000000 [2,3,5,7,11,13]</lang>
J
<lang J> mp =: $:~ :(+/ .*) NB. matrix product f =: (mp 0 = [: */ 3 5 |/ ])@:i. assert 233168 -: f 1000 NB. ****************** THIS IS THE ANSWER FOR 1000 </lang> For the efficient computation with large n, we start with observation that the sum of these multiples with the reversed list follows a pattern. <lang J> g =: #~ (0 = [: */ 3 5&(|/)) assert 0 3 5 6 9 10 12 15 18 20 21 24 25 27 30 33 35 36 39 40 42 45 48 -: g i. 50 assert 48 48 47 46 48 46 47 48 48 47 46 48 46 47 48 48 47 46 48 46 47 48 48 -: (+ |.)g i. 50 NB. the pattern
assert (f -: -:@:(+/)@:(+|.)@:g@:i.) 50 NB. half sum of the pattern.
NB. continue... </lang> Stealing the idea from the python implementation to use 3 simple patterns rather than 1 complicated pattern, <lang J>
first =: 0&{
last =: first + skip * <.@:(skip %~ <:@:(1&{) - first)
skip =: 2&{
terms =: >:@:<.@:(skip %~ last - first)
sum_arithmetic_series =: -:@:(terms * first + last) NB. sum_arithmetic_series FIRST LAST SKIP
NB. interval is [FIRST, LAST)
NB. sum_arithmetic_series is more general than required.
(0,.10 10000 10000000000000000000x)(,"1 0"1 _)3 5 15x NB. demonstration: form input vectors for 10, ten thousand, and 1*10^(many)
0 10 3 0 10 5 0 10 15
0 10000 3 0 10000 5 0 10000 15
0 10000000000000000000 3 0 10000000000000000000 5 0 10000000000000000000 15
(0,.10 10000 10000000000000000000x)+`-/"1@:(sum_arithmetic_series"1@:(,"1 0"1 _))3 5 15x
23 23331668 23333333333333333331666666666666666668 </lang>
Java
<lang Java>class Experiment { public static long getSum(long n) { long sum = 0; for (int i = 3; i < n; i++) { if (i % 3 == 0 || i % 5 == 0) sum += i; } return sum; } public static void main(String[] args) { System.out.println(getSum(1000)); } }</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
return sum_mults(3, maxLimit) + sum_mults(5, maxLimit) - sum_mults(15, maxLimit)
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method runSample(arg) private static
offset = 30 incr = 10
say 'Limit'.right(offset) || '|' || 'Sum' say '-'.copies(offset) || '+' || '-'.copies(60) timing = System.nanoTime sum = summing() timing = System.nanoTime - timing say 1000.format.right(offset)'|'sum say 'Elapsed time:' Rexx(timing * 1e-9).format(4, 6)'s' say
say 'Limit'.right(offset) || '|' || 'Sum' say '-'.copies(offset) || '+' || '-'.copies(60) tmax = 1e+6 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
say 'Limit'.right(offset) || '|' || 'Sum' say '-'.copies(offset) || '+' || '-'.copies(60) timing = System.nanoTime sum = sum35(1000) timing = System.nanoTime - timing say 1000.format.right(offset)'|'sum say 'Elapsed time:' Rexx(timing * 1e-9).format(4, 6)'s' say
say 'Limit'.right(offset) || '|' || 'Sum' say '-'.copies(offset) || '+' || '-'.copies(60) tmax = 1e+27 timing = System.nanoTime mm = 1 loop while mm <= tmax 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:
Limit|Sum
------------------------------+------------------------------------------------------------
1000|233168
Elapsed time: 0.097668s
Limit|Sum
------------------------------+------------------------------------------------------------
1|0
10|23
100|2318
1000|233168
10000|23331668
100000|2333316668
1000000|233333166668
Elapsed time: 11.593837s
Limit|Sum
------------------------------+------------------------------------------------------------
1000|233168
Elapsed time: 0.000140s
Limit|Sum
------------------------------+------------------------------------------------------------
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
100000000000000000000|2333333333333333333316666666666666666668
1000000000000000000000|233333333333333333333166666666666666666668
10000000000000000000000|23333333333333333333331666666666666666666668
100000000000000000000000|2333333333333333333333316666666666666666666668
1000000000000000000000000|233333333333333333333333166666666666666666666668
10000000000000000000000000|23333333333333333333333331666666666666666666666668
100000000000000000000000000|2333333333333333333333333316666666666666666666666668
1000000000000000000000000000|233333333333333333333333333166666666666666666666666668
Elapsed time: 0.005545s
МК-61/52
- МК-61/52:
<lang>П1 0 П0 3 П4 ИП4 3 / {x} x#0 17 ИП4 5 / {x} x=0 21 ИП0 ИП4 + П0 КИП4 ИП1 ИП4 - x=0 05 ИП0 С/П</lang>
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 == sc # python tests aren't like those of c.
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)))
- Scalability
p = 20 print('\nFor n = %20i -> %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 For n = 100000000000000000000 -> 2333333333333333333316666666666666666668
Racket
<lang racket>
- lang racket
(require math)
- A naive solution
(define (naive k)
(for/sum ([n (expt 10 k)]
#:when (or (divides? 3 n) (divides? 5 n)))
n))
(for/list ([k 7]) (naive k))
- Using the formula for an arithmetic sum
(define (arithmetic-sum a1 n Δa)
; returns a1+a2+...+an (define an (+ a1 (* (- n 1) Δa))) (/ (* n (+ a1 an)) 2))
(define (analytical k)
(define 10^k (expt 10 k))
(define (n d) (quotient (- 10^k 1) d))
(+ (arithmetic-sum 3 (n 3) 3)
(arithmetic-sum 5 (n 5) 5)
(- (arithmetic-sum 15 (n 15) 15))))
(for/list ([k 20]) (analytical k)) </lang> Output: <lang racket> '(0 23 2318 233168 23331668 2333316668 233333166668) '(0
23 2318 233168 23331668 2333316668 233333166668 23333331666668 2333333316666668 233333333166666668 23333333331666666668 2333333333316666666668 233333333333166666666668 23333333333331666666666668 2333333333333316666666666668 233333333333333166666666666668 23333333333333331666666666666668 2333333333333333316666666666666668 233333333333333333166666666666666668 23333333333333333331666666666666666668)
</lang>
REXX
version 1
<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
version 2
<lang rexx>/* REXX ***************************************************************
- Translation from Perl6->NetRexx->REXX
- 15.05.2013 Walter Pachl
- /
Numeric Digits 100 call time 'R' n=1 Do i=1 To 30
Say right(n,30) sum35(n) n=n*10 End
Say time('E') 'seconds' Exit
sum35: Procedure
Parse Arg maxLimit return sum_mults(3, maxLimit) + sum_mults(5, maxLimit) - sum_mults(15, maxLimit)
sum_mults: Procedure
Parse Arg first, limit last = limit - 1 last = last - last // first sum = (last % first) * (first + last) % 2 return sum</lang>
Output:
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
100000000000000000000 2333333333333333333316666666666666666668
1000000000000000000000 233333333333333333333166666666666666666668
10000000000000000000000 23333333333333333333331666666666666666666668
100000000000000000000000 2333333333333333333333316666666666666666666668
1000000000000000000000000 233333333333333333333333166666666666666666666668
10000000000000000000000000 23333333333333333333333331666666666666666666666668
100000000000000000000000000 2333333333333333333333333316666666666666666666666668
1000000000000000000000000000 233333333333333333333333333166666666666666666666666668
10000000000000000000000000000 23333333333333333333333333331666666666666666666666666668
100000000000000000000000000000 2333333333333333333333333333316666666666666666666666666668
0 milliseconds with rexx m35a > m35a.txt
46 millisecond with rexx m35a
Run BASIC
<lang runbasic>print multSum35(1000) end function multSum35(n)
for i = 1 to n - 1
If (i mod 3 = 0) or (i mod 5 = 0) then multSum35 = multSum35 + i
next i
end function</lang>
233168
Scala
<lang scala>def sum35( max:BigInt ) : BigInt = max match {
// Simplest solution but limited to Ints only
case j if j < 100000 => (1 until j.toInt).filter( i => i % 3 == 0 || i % 5 == 0 ).sum
// Using a custom iterator that takes Longs
case j if j < 10e9.toLong => {
def stepBy( step:Long ) : Iterator[Long] = new Iterator[Long] { private var i = step; def hasNext = true; def next() : Long = { val result = i; i = i + step; result } }
stepBy(3).takeWhile( _< j ).sum + stepBy(5).takeWhile( _< j ).sum - stepBy(15).takeWhile( _< j ).sum
}
// Using the formula for a Triangular number
case j => {
def triangle( i:BigInt ) = i * (i+1) / BigInt(2)
3 * triangle( (j-1)/3 ) + 5 * triangle( (j-1)/5 ) - 15 * triangle( (j-1)/15 )
}
}
{ for( i <- (0 to 20); n = "1"+"0"*i ) println( (" " * (21 - i)) + n + " => " + (" " * (21 - i)) + sum35(BigInt(n)) ) }</lang>
- Output:
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
100000000000000000000 => 2333333333333333333316666666666666666668
Scheme
<lang scheme>(fold (lambda (x tot) (+ tot (if (or (zero? (remainder x 3)) (zero? (remainder x 5))) x 0))) 0 (iota 1000))</lang>
Output:
233168
Or, more clearly by decomposition:
<lang scheme>(define (fac35? x)
(or (zero? (remainder x 3))
(zero? (remainder x 5))))
(define (fac35filt x tot)
(+ tot (if (fac35? x) x 0)))
(fold fac35filt 0 (iota 1000))</lang>
Output:
233168
For larger numbers iota can take quite a while just to build the list -- forget about waiting for all the computation to finish!
<lang scheme>(define (trisum n fac)
(let* ((n1 (quotient (- n 1) fac))
(n2 (+ n1 1)))
(quotient (* fac n1 n2) 2)))
(define (fast35sum n)
(- (+ (trisum n 5) (trisum n 3)) (trisum n 15)))
(fast35sum 1000) (fast35sum 100000000000000000000) </lang>
Output:
233168 2333333333333333333316666666666666666668
Seed7
<lang seed7>$ include "seed7_05.s7i";
include "bigint.s7i";
const func bigInteger: sum35 (in bigInteger: n) is func
result
var bigInteger: sum35 is 0_;
local
const func bigInteger: sumMul (in bigInteger: n, in bigInteger: f) is func
result
var bigInteger: sumMul is 0_;
local
var bigInteger: n1 is 0_;
begin
n1 := pred(n) div f;
sumMul := f * n1 * succ(n1) div 2_;
end func;
begin
sum35 := sumMul(n, 3_) + sumMul(n, 5_) - sumMul(n, 15_);
end func;
const proc: main is func
begin writeln(sum35(1000_)); writeln(sum35(10_ ** 20)); end func;</lang>
- Output:
233168 2333333333333333333316666666666666666668
Tcl
<lang tcl># Fairly simple version; only counts by 3 and 5, skipping intermediates proc mul35sum {n} {
for {set total [set threes [set fives 0]]} {$threes<=$n||$fives<=$n} {} {
if {$threes<$fives} { incr total $threes incr threes 3 } elseif {$threes>$fives} { incr total $fives incr fives 5 } else { incr total $threes incr threes 3 incr fives 5 }
} return $total
}</lang> However, that's pretty dumb. We can do much better by observing that the sum of the multiples of below some is , where is the 'th triangular number, for which there exists a trivial formula. Then we simply use an overall formula of (that is, summing the multiples of three and the multiples of five, and then subtracting the multiples of 15 which were double-counted). <lang tcl># Smart version; no iteration so very scalable! proc tcl::mathfunc::triangle {n} {expr {
$n * ($n+1) / 2
}}
- Note that the rounding on integer division is exactly what we need here.
proc sum35 {n} {expr {
3*triangle($n/3) + 5*triangle($n/5) - 15*triangle($n/15)
}}</lang> Demonstrating: <lang tcl>puts [mul35sum 1000],[sum35 1000] puts [mul35sum 10000000],[sum35 10000000]
- Just the quick one; waiting for the other would get old quickly...
puts [sum35 100000000000000000000]</lang>
- Output:
234168,234168 23333341666668,23333341666668 2333333333333333333416666666666666666668