Sum multiples of 3 and 5: Difference between revisions
Keithpinson (talk | contribs) m Removed "Insert formula here" added accidentally (I guess) when RunBasic Added |
|||
Line 308: | Line 308: | ||
=={{header|Mathematica}}== |
=={{header|Mathematica}}== |
||
<lang mathematica>sum35[n_] := |
|||
{{incorrect|Mathematica|Functions of n required instead of hard-coding 1000 and 1e20.}} |
|||
Sum[k, {k, 3, n - 1, 3}] + Sum[k, {k, 5, n - 1, 5}] - |
|||
<lang mathematica>Total[Select[Range[1000-1],Divisible[#,3]||Divisible[#,5]&]]</lang> |
|||
Sum[k, {k, 15, n - 1, 15}] |
|||
sum35[1000]</lang> |
|||
{{out}} |
{{out}} |
||
<pre>233168</pre> |
<pre>233168</pre> |
||
<lang mathematica> |
<lang mathematica>sum35[10^20]</lang> |
||
{{out}} |
{{out}} |
||
<pre>233333333333333333333166666666666666666668</pre> |
<pre>233333333333333333333166666666666666666668</pre> |
Revision as of 23:41, 8 June 2013
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
FBSL
Derived from BASIC version <lang qbasic>#APPTYPE CONSOLE
FUNCTION sumOfThreeFiveMultiples(n AS INTEGER)
DIM sum AS INTEGER FOR DIM i = 1 TO n - 1 IF (NOT (i MOD 3)) OR (NOT (i MOD 5)) THEN INCR(sum, i) END IF NEXT RETURN sum
END FUNCTION
PRINT sumOfThreeFiveMultiples(1000) PAUSE </lang> Output
233168 Press any key to continue...
Forth
<lang forth>: main ( n -- )
0 swap 3 do i 3 mod 0= if i + else i 5 mod 0= if i + then then loop . ;
1000 main \ 233168 ok</lang>
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 SumMultiples { 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
Mathematica
<lang mathematica>sum35[n_] :=
Sum[k, {k, 3, n - 1, 3}] + Sum[k, {k, 5, n - 1, 5}] - Sum[k, {k, 15, n - 1, 15}]
sum35[1000]</lang>
- Output:
233168
<lang mathematica>sum35[10^20]</lang>
- Output:
233333333333333333333166666666666666666668
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
<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>
Input: n.
Output for n = 1000: 233168.
Perl
<lang Perl>#!/usr/bin/perl use strict ; use warnings ; use List::Util qw( sum ) ;
sub sum_3_5 {
my $limit = shift ; return sum grep { $_ % 3 == 0 || $_ % 5 == 0 } ( 1..$limit - 1 ) ;
}
print "The sum is " . sum_3_5( 1000 ) . " !\n" ;</lang>
- Output:
The sum is 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]
- 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