Sum multiples of 3 and 5
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.
You are encouraged to solve this task according to the task description, using any language you may know.
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
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 = 234168
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 </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>
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
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)))
- 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
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:
<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