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
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 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, then iota can take quite a while. But once decomposed, iteration is pretty easily done.
<lang scheme> (define m 100000000000000000000) (let loop ((x 1)(tot 0))
(if (> x m) tot (loop (+ 1 x) (fac35filt x tot))))</lang>
Output? (still waiting...)
Tcl
<lang tcl># Simple version 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
}
- Smart version; multiply triangular numbers by a factor to do the summing of products
proc sum35 {n} {
expr {3*($n/3*($n/3+1)/2) + 5*($n/5*($n/5+1)/2) - 15*($n/15*($n/15+1)/2)}
}</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