# Sum multiples of 3 and 5: Difference between revisions

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`

## AWK

 This example is incorrect. Please fix the code and remove this message.Details: Extra credit answer is 2333333333333333333316666666666666666668

Save this into file "sum_multiples_of3and5.awk" <lang AWK>#!/usr/bin/awk -f { n = \$1-1; printf("%.60g\n",sum(n,3)+sum(n,5)-sum(n,15)); } function sum(n,d) { m = int(n/d); return (d*m*(m+1)/2); }</lang> Output of Gawk 4.0.1 and mawk

```\$ echo -e '1000\n1e20' |awk -f sum_multiples_of3and5.awk
233168
2333333333333332940795175780693005303808```

## BASIC

Works with: FreeBASIC

<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#

The following C# 5 / .Net 4 code is an efficient solution in that it does not iterate through the numbers 1 ... n - 1 in order to calculate the answer. On the other hand, the System.Numerics.BigInteger class (.Net 4 and upwards) is not itself efficient because calculations take place in software instead of hardware. Consequently, it may be faster to conduct the calculation for smaller values with native ("primitive") types using a 'brute force' iteration approach.

<lang csharp> using System; using System.Collections.Generic; using System.Numerics;

namespace RosettaCode {

```   class Program
{
static void Main()
{
List<BigInteger> candidates = new List<BigInteger>(new BigInteger[] { 1000, 100000, 10000000, 10000000000, 1000000000000000 });
```
```           foreach (BigInteger candidate in candidates)
{
BigInteger c = candidate - 1;
```
```               Console.WriteLine("The sum of numbers divisible by 3 or 5 between 1 and {0} is {1}", c, answer3 + answer5 - answer15);
}
```
```           Console.ReadKey(true);
}
```
```       private static BigInteger GetSumOfNumbersDivisibleByN(BigInteger candidate, uint n)
{
BigInteger largest = candidate;
while (largest % n > 0)
largest--;
BigInteger totalCount = (largest / n);
BigInteger pairCount = totalCount / 2;
bool unpairedNumberOnFoldLine = (totalCount % 2 == 1);
BigInteger pairSum = largest + n;
return pairCount * pairSum + (unpairedNumberOnFoldLine ? pairSum / 2 : 0);
}
```
```   }
```

} </lang>

Output:

The sum of numbers divisible by 3 or 5 between 1 and 999 is 233168

The sum of numbers divisible by 3 or 5 between 1 and 99999 is 2333316668

The sum of numbers divisible by 3 or 5 between 1 and 9999999 is 23333331666668

The sum of numbers divisible by 3 or 5 between 1 and 9999999999 is 23333333331666666668

The sum of numbers divisible by 3 or 5 between 1 and 999999999999999 is 233333333333333166666666666668

The sum of numbers divisible by 3 or 5 between 1 and 99999999999999999999 is 2333333333333333333316666666666666666668

## C++

<lang cpp>

1. 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
```

## Clojure

Unoptimized <lang clojure>(defn sum-multiples

```   ([n] (sum-multiples (dec n) 0))
([n sum]
(if (< n 3)
sum
(if (or (= 0 (mod n 3)) (= 0 (mod n 5)))
(recur (dec n) (+ sum n))
(recur (dec n) sum)))))</lang>
```

## 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
```

</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
```

## Component Pascal

BlackBox Component Builder <lang oberon2> MODULE Sum3_5; IMPORT StdLog, Strings, Args;

PROCEDURE DoSum(n: INTEGER):INTEGER; VAR i,sum: INTEGER; BEGIN sum := 0;i := 0; WHILE (i < n) DO IF (i MOD 3 = 0) OR (i MOD 5 = 0) THEN INC(sum,i) END; INC(i) END; RETURN sum END DoSum;

PROCEDURE Compute*; VAR params: Args.Params; i,n,res: INTEGER; BEGIN Args.Get(params); Strings.StringToInt(params.args[0],n,res); StdLog.String("Sum: ");StdLog.Int(DoSum(n)); StdLog.Ln END Compute;

END Sum3_5. </lang> Execute: ^Q Sum3_5.Compute 1000 ~
Output:

```Sum:  233168
```

## 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 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```

## Déjà Vu

<lang dejavu>sum-divisible n: 0 for i range 1 -- n: if or = 0 % i 3 = 0 % i 5: + i

!. sum-divisible 1000</lang>

Output:
`233168`

## Erlang

<lang erlang>sum_3_5(X) when is_number(X) -> sum_3_5(erlang:round(X)-1, 0). sum_3_5(X, Total) when X < 3 -> Total; sum_3_5(X, Total) when X rem 3 =:= 0 orelse X rem 5 =:= 0 ->

``` sum_3_5(X-1, Total+X);
```

sum_3_5(X, Total) ->

``` sum_3_5(X-1, Total).
```

io:format("~B~n", [sum_3_5(1000)]).</lang>

Output:
`233168`

## F#

Translation of: Perl 6

<lang fsharp>let sum35 (n: int) =

```   Seq.init n (fun i -> i)
|> Seq.fold (fun sum i -> if i % 3 = 0 || i % 5 = 0 then sum + i else sum) 0
```

printfn "%d" (sum35 1000) printfn "----------"

let sumUpTo (n : bigint) = n * (n + 1I) / 2I

let sumMultsBelow k n = k * (sumUpTo ((n-1I)/k))

let sum35fast n = (sumMultsBelow 3I n) + (sumMultsBelow 5I n) - (sumMultsBelow 15I n)

[for i = 0 to 30 do yield i] |> List.iter (fun i -> printfn "%A" (sum35fast (bigint.Pow(10I, i))))</lang>

Output:
```233168
----------
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```

## 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>

Another FORTH version using the Inclusion/Exclusion Principle. The result is a double precision integer (128 bits on a 64 bit computer) which lets us calculate up to 10^18 (the max precision of a single precision 64 bit integer) Since this is Project Euler problem 1, the name of the main function is named euler1tower.

<lang forth>: third 2 pick ;

>dtriangular ( n -- d )
```   dup 1+ m* d2/ ;
```
sumdiv ( n m -- d )
```   dup >r / >dtriangular r> 1 m*/ ;
```
sumdiv_3,5 ( n -- n )
```   dup 3 sumdiv third 5 sumdiv d+ rot 15 sumdiv d- ;
```
euler1 ( -- n )
```   999 sumdiv_3,5 drop ;
```
euler1tower ( -- )
```   1  \ power of 10
19 0 DO
cr dup 19 .r space dup 1- sumdiv_3,5 d.
10 *
LOOP drop ;
```

euler1 . 233168 ok euler1tower

```                 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 ok </lang>

## Groovy

<lang groovy>def sumMul = { n, f -> BigInteger n1 = (n - 1) / f; f * n1 * (n1 + 1) / 2 } def sum35 = { sumMul(it, 3) + sumMul(it, 5) - sumMul(it, 15) }</lang> Test Code: <lang groovy>[(1000): 233168, (10e20): 233333333333333333333166666666666666666668].each { arg, value ->

```   println "Checking \$arg == \$value"
assert sum35(arg) == value
```

}</lang>

Output:
```Checking 1000 == 233168
Checking 1.0E+21 == 233333333333333333333166666666666666666668```

Template: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>
```
Output:
```233168
2333333333333333333333333333333316666666666666666666666666666668
233168
41426953573049```

## Icon and Unicon

The following works in both langauges.

<lang unicon>procedure main(A)

```   n := (integer(A[1]) | 1000)-1
write(sum(n,3)+sum(n,5)-sum(n,15))
```

end

procedure sum(n,m)

```   return m*((n/m)*(n/m+1)/2)
```

end</lang>

Sample output:

```->sm35
233168
->sm35 100000000000000000000
2333333333333333333316666666666666666668
->
```

## 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`

## Lasso

<lang Lasso>local(limit = 1) while(#limit <= 100000) => {^ local(s = 0) loop(-from=3,-to=#limit-1) => { not (loop_count % 3) || not (loop_count % 5) ? #s += loop_count } 'The sum of multiples of 3 or 5 between 1 and '+(#limit-1)+' is: '+#s+'\r' #limit = integer(#limit->asString + '0') ^}</lang>

Output:
```The sum of multiples of 3 or 5 between 1 and 0 is: 0
The sum of multiples of 3 or 5 between 1 and 9 is: 23
The sum of multiples of 3 or 5 between 1 and 99 is: 2318
The sum of multiples of 3 or 5 between 1 and 999 is: 233168
The sum of multiples of 3 or 5 between 1 and 9999 is: 23331668
The sum of multiples of 3 or 5 between 1 and 99999 is: 2333316668```

## Limbo

Uses the IPints library when the result will be very large.

<lang Limbo>implement Sum3and5;

include "sys.m"; sys: Sys; include "draw.m"; include "ipints.m"; ipints: IPints; IPint: import ipints;

Sum3and5: module { init: fn(nil: ref Draw->Context, args: list of string); };

ints: array of ref IPint;

init(nil: ref Draw->Context, args: list of string) { sys = load Sys Sys->PATH; ipints = load IPints IPints->PATH;

# We use 1, 2, 3, 5, and 15: ints = array[16] of ref IPint; for(i := 0; i < len ints; i++) ints[i] = IPint.inttoip(i);

args = tl args; while(args != nil) { h := hd args; args = tl args; # If it's big enough that the result might not # fit inside a big, we use the IPint version. if(len h > 9) { sys->print("%s\n", isum3to5(IPint.strtoip(h, 10)).iptostr(10)); } else { sys->print("%bd\n", sum3to5(big h)); } } }

triangle(n: big): big { return((n * (n + big 1)) / big 2); }

sum_multiples(n: big, limit: big): big { return(n * triangle((limit - big 1) / n)); }

sum3to5(limit: big): big { return( sum_multiples(big 3, limit) + sum_multiples(big 5, limit) - sum_multiples(big 15, limit)); }

itriangle(n: ref IPint): ref IPint { return n.mul(n.add(ints[1])).div(ints[2]).t0; }

isum_multiples(n: ref IPint, limit: ref IPint): ref IPint { return n.mul(itriangle(limit.sub(ints[1]).div(n).t0)); }

isum3to5(limit: ref IPint): ref IPint { return( isum_multiples(ints[3], limit). add(isum_multiples(ints[5], limit)). sub(isum_multiples(ints[15], limit))); } </lang>

Output:
```% sum3and5 1000 100000000000000000000
233168
2333333333333333333316666666666666666668```

## 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`

Another alternative is <lang mathematica> Union @@ Range[0, 999, {3, 5}] // Tr </lang>

## MATLAB / Octave

 This example is incorrect. Please fix the code and remove this message.Details: Extra credit answer is 2333333333333333333316666666666666666668
 This example is incorrect. Please fix the code and remove this message.Details: Extra credit answer is 2333333333333333333316666666666666666668

<lang MATLAB>n=1:999; sum(n(mod(n,3)==0 | mod(n,5)==0))</lang>

`ans =  233168`

Another alternative is <lang MATLAB>n=1000; sum(0:3:n-1)+sum(0:5:n-1)-sum(0:15:n-1)</lang> Of course, its more efficient to use Gauss' approach of adding subsequent integers <lang MATLAB>n=1e20-1; n3=floor(n/3); n5=floor(n/5); n15=floor(n/15); (3*n3*(n3+1) + 5*n5*(n5+1) - 15*n15*(n15+1))/2</lang>

```ans =  2.33333333333333e+39
```

## Maxima

<lang Maxima>sumi(n, incr):= block([kmax: quotient(n, incr)],

``` (ev(sum(incr*k, k, 1, kmax), simpsum)));
```

sum35(n):=sumi(n, 3) + sumi(n, 5) - sumi(n, 15);

sum35(1000); sum35(10^20);</lang> Output:

```(%i16) sum35(1000);
(%o16)                              234168
(%i17) sum35(10^20);
(%o17)             2333333333333333333416666666666666666668```

## 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.

## PARI/GP

<lang parigp>ct(n,k)=n=n\k;k*n*(n+1)/2; a(n)=ct(n,3)+ct(n,5)-ct(n,15); a(1000) a(1e20)</lang>

Output:
```%1 = 234168
%2 = 2333333333333333333416666666666666666668```

## 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```

## Powershell

Here is a cmdet that will provide the sum of unique multiples of any group of numbers below a given limit. I haven't attempted the extra credit here as the math is too complex for me at the moment. <lang Powershell>function Get-SumOfMultiples {

```   Param
(
[Parameter(
Position=0)]
\$Cap = 1000,
```
```       [Parameter(
ValueFromRemainingArguments=\$True)]
\$Multiplier = (3,5)
)
```
```   \$Multiples = @()
\$Sum = 0
\$multiplier |
ForEach-Object {
For(\$i = 1; \$i -lt \$Cap; \$i ++)
{
If(\$i % \$_ -eq 0)
{\$Multiples += \$i}
}
}
```
```    \$Multiples |
select -Unique |
ForEach-Object {
\$Sum += \$_
}
\$Sum
```

}</lang>

Output:
`Get-SumOfMultiples`
`233168`
Output:
`Get-SumOfMultiples 1500 3 5 7 13`
`649444`

## Prolog

### Slow version

<lang Prolog>sum_of_multiples_of_3_and_5_slow(N, TT) :- sum_of_multiples_of_3_and_5(N, 1, 0, TT).

sum_of_multiples_of_3_and_5(N, K, S, S) :- 3 * K >= N.

sum_of_multiples_of_3_and_5(N, K, C, S) :- T3 is 3 * K, T3 < N, C3 is C + T3, T5 is 5 * K, ( (T5 < N, K mod 3 =\= 0) -> C5 is C3 + T5 ; C5 = C3), K1 is K+1, sum_of_multiples_of_3_and_5(N, K1, C5, S).

</lang>

### Fast version

<lang Polog>sum_of_multiples_of_3_and_5_fast(N, TT):- maplist(compute_sum(N), [3,5,15], [TT3, TT5, TT15]), TT is TT3 + TT5 - TT15.

compute_sum(N, N1, Sum) :- ( N mod N1 =:= 0 -> N2 is N div N1 - 1 ; N2 is N div N1), Sum is N1 * N2 * (N2 + 1) / 2. </lang>

Output :

``` ?- sum_of_multiples_of_3_and_5_slow(1000, TT).
TT = 233168 .

?- sum_of_multiples_of_3_and_5_fast(100000000000000000000, TT).
TT = 2333333333333333333316666666666666666668.
```

## 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]
```
1. 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))

1. Pretty patterns

for p in range(7):

```   print('For n = %7i -> %i' % (10**p, sum35c(10**p)))
```
1. 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```

## R

<lang rsplus>m35 = function(n) sum(unique(c(

```   seq(3, n-1, by = 3), seq(5, n-1, by = 5))))
```

m35(1000) # 233168</lang>

## Racket

<lang racket>

1. 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```

### version 3

This version automatically adjusts the numeric digits.
A little extra code was added to format the output nicely.
The formula used is a form of the Gauss Summation formula. <lang rexx>/*REXX pgm sums all integers from 1──>N─1 that're multiples of 3 or 5.*/ parse arg N t .; if N== then N=1000; if t== then t=1 numeric digits 9999; numeric digits max(9,20*length(N*10**t)) say 'The sum of all positive integers that are a multiple of 3 and 5 are:' say /* [↓] change the look of nE+nn */

```     do t;  parse value format(N,2,1,,0) 'E0'   with  y 'E' _ .;    _=_+0
y=right((m/1)'e'_,5)'-1'  /*allows for a bug in some REXXes*/
if t==1  then y=N-1       /*handle special case of one-time*/
sum=sumDivisors(N-1,3) + sumDivisors(N-1,5) - sumDivisors(N-1,3*5)
say 'integers from  1 ──►'   y   " is "    sum
N=N*10                           /*multiply by ten for next round.*/
end   /*t*/
```

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────SUMDIVISORS subroutine──────────────*/ sumDivisors: procedure; parse arg x,d; _=x%d; return d*_*(_+1)%2</lang> output when using the default input:

```The sum of all positive integers that are a multiple of 3 and 5 are:

integers from  1 ──► 999  is  233168
```

output when using the input of: 1 80

```The sum of all positive integers that are a multiple of 3 and 5 are:

integers from  1 ──►     1-1  is  0
integers from  1 ──►   1e1-1  is  23
integers from  1 ──►   1e2-1  is  2318
integers from  1 ──►   1e3-1  is  233168
integers from  1 ──►   1e4-1  is  23331668
integers from  1 ──►   1e5-1  is  2333316668
integers from  1 ──►   1e6-1  is  233333166668
integers from  1 ──►   1e7-1  is  23333331666668
integers from  1 ──►   1e8-1  is  2333333316666668
integers from  1 ──►   1e9-1  is  233333333166666668
integers from  1 ──►  1e10-1  is  23333333331666666668
integers from  1 ──►  1e11-1  is  2333333333316666666668
integers from  1 ──►  1e12-1  is  233333333333166666666668
integers from  1 ──►  1e13-1  is  23333333333331666666666668
integers from  1 ──►  1e14-1  is  2333333333333316666666666668
integers from  1 ──►  1e15-1  is  233333333333333166666666666668
integers from  1 ──►  1e16-1  is  23333333333333331666666666666668
integers from  1 ──►  1e17-1  is  2333333333333333316666666666666668
integers from  1 ──►  1e18-1  is  233333333333333333166666666666666668
integers from  1 ──►  1e19-1  is  23333333333333333331666666666666666668
integers from  1 ──►  1e20-1  is  2333333333333333333316666666666666666668
integers from  1 ──►  1e21-1  is  233333333333333333333166666666666666666668
integers from  1 ──►  1e22-1  is  23333333333333333333331666666666666666666668
integers from  1 ──►  1e23-1  is  2333333333333333333333316666666666666666666668
integers from  1 ──►  1e24-1  is  233333333333333333333333166666666666666666666668
integers from  1 ──►  1e25-1  is  23333333333333333333333331666666666666666666666668
integers from  1 ──►  1e26-1  is  2333333333333333333333333316666666666666666666666668
integers from  1 ──►  1e27-1  is  233333333333333333333333333166666666666666666666666668
integers from  1 ──►  1e28-1  is  23333333333333333333333333331666666666666666666666666668
integers from  1 ──►  1e29-1  is  2333333333333333333333333333316666666666666666666666666668
integers from  1 ──►  1e30-1  is  233333333333333333333333333333166666666666666666666666666668
integers from  1 ──►  1e31-1  is  23333333333333333333333333333331666666666666666666666666666668
integers from  1 ──►  1e32-1  is  2333333333333333333333333333333316666666666666666666666666666668
integers from  1 ──►  1e33-1  is  233333333333333333333333333333333166666666666666666666666666666668
integers from  1 ──►  1e34-1  is  23333333333333333333333333333333331666666666666666666666666666666668
integers from  1 ──►  1e35-1  is  2333333333333333333333333333333333316666666666666666666666666666666668
integers from  1 ──►  1e36-1  is  233333333333333333333333333333333333166666666666666666666666666666666668
integers from  1 ──►  1e37-1  is  23333333333333333333333333333333333331666666666666666666666666666666666668
integers from  1 ──►  1e38-1  is  2333333333333333333333333333333333333316666666666666666666666666666666666668
integers from  1 ──►  1e39-1  is  233333333333333333333333333333333333333166666666666666666666666666666666666668
integers from  1 ──►  1e40-1  is  23333333333333333333333333333333333333331666666666666666666666666666666666666668
integers from  1 ──►  1e41-1  is  2333333333333333333333333333333333333333316666666666666666666666666666666666666668
integers from  1 ──►  1e42-1  is  233333333333333333333333333333333333333333166666666666666666666666666666666666666668
integers from  1 ──►  1e43-1  is  23333333333333333333333333333333333333333331666666666666666666666666666666666666666668
integers from  1 ──►  1e44-1  is  2333333333333333333333333333333333333333333316666666666666666666666666666666666666666668
integers from  1 ──►  1e45-1  is  233333333333333333333333333333333333333333333166666666666666666666666666666666666666666668
integers from  1 ──►  1e46-1  is  23333333333333333333333333333333333333333333331666666666666666666666666666666666666666666668
integers from  1 ──►  1e47-1  is  2333333333333333333333333333333333333333333333316666666666666666666666666666666666666666666668
integers from  1 ──►  1e48-1  is  233333333333333333333333333333333333333333333333166666666666666666666666666666666666666666666668
integers from  1 ──►  1e49-1  is  23333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666668
integers from  1 ──►  1e50-1  is  2333333333333333333333333333333333333333333333333316666666666666666666666666666666666666666666666668
integers from  1 ──►  1e51-1  is  233333333333333333333333333333333333333333333333333166666666666666666666666666666666666666666666666668
integers from  1 ──►  1e52-1  is  23333333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e53-1  is  2333333333333333333333333333333333333333333333333333316666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e54-1  is  233333333333333333333333333333333333333333333333333333166666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e55-1  is  23333333333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e56-1  is  2333333333333333333333333333333333333333333333333333333316666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e57-1  is  233333333333333333333333333333333333333333333333333333333166666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e58-1  is  23333333333333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e59-1  is  2333333333333333333333333333333333333333333333333333333333316666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e60-1  is  233333333333333333333333333333333333333333333333333333333333166666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e61-1  is  23333333333333333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e62-1  is  2333333333333333333333333333333333333333333333333333333333333316666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e63-1  is  233333333333333333333333333333333333333333333333333333333333333166666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e64-1  is  23333333333333333333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e65-1  is  2333333333333333333333333333333333333333333333333333333333333333316666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e66-1  is  233333333333333333333333333333333333333333333333333333333333333333166666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e67-1  is  23333333333333333333333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e68-1  is  2333333333333333333333333333333333333333333333333333333333333333333316666666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e69-1  is  233333333333333333333333333333333333333333333333333333333333333333333166666666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e70-1  is  23333333333333333333333333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e71-1  is  2333333333333333333333333333333333333333333333333333333333333333333333316666666666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e72-1  is  233333333333333333333333333333333333333333333333333333333333333333333333166666666666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e73-1  is  23333333333333333333333333333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e74-1  is  2333333333333333333333333333333333333333333333333333333333333333333333333316666666666666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e75-1  is  233333333333333333333333333333333333333333333333333333333333333333333333333166666666666666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e76-1  is  23333333333333333333333333333333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e77-1  is  2333333333333333333333333333333333333333333333333333333333333333333333333333316666666666666666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e78-1  is  233333333333333333333333333333333333333333333333333333333333333333333333333333166666666666666666666666666666666666666666666666666666666666666666666666666668
integers from  1 ──►  1e79-1  is  23333333333333333333333333333333333333333333333333333333333333333333333333333331666666666666666666666666666666666666666666666666666666666666666666666666666668
```

## Ruby

<lang ruby>

1. Given two integers n1,n2 return sum of multiples upto n3
2. Nigel_Galloway
3. August 24th., 2013.

def g(n1, n2, n3)

```  g1 = n1*n2
(1..g1).select{|x| x%n1==0 or x%n2==0}.collect{|x| g2=(n3-x)/g1; (x+g1*g2+x)*(g2+1)}.inject{|sum,x| sum+x}/2
```

end </lang>

Output:

<lang ruby> puts g(3,5,999) </lang>

```233168
```

<lang ruby>

1. For extra credit

puts g(3,5,100000000000000000000-1) </lang>

```2333333333333333333316666666666666666668
```

## 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 ${\displaystyle k}$ below some ${\displaystyle n}$ is ${\displaystyle kT_{n/k}}$, where ${\displaystyle T_{i}}$ is the ${\displaystyle i}$'th triangular number, for which there exists a trivial formula. Then we simply use an overall formula of ${\displaystyle 3T_{n/3}+5T_{n/5}-15T_{n/15}}$ (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
```

}}

1. 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]

1. Just the quick one; waiting for the other would get old quickly...

puts [sum35 100000000000000000000]</lang>

Output:
```234168,234168
23333341666668,23333341666668
2333333333333333333416666666666666666668
```

## Wortel

<lang wortel>@let {

``` sum35 ^(@sum \!-@(\~%%3 || \~%%5) @til)
```
``` !sum35 1000 ; returns 233168
```

}</lang>

## XPL0

<lang XPL0>include c:\cxpl\stdlib;

func Sum1; \Return sum the straightforward way int N, S; [S:= 0; for N:= 1 to 999 do

```   if rem(N/3)=0 or rem(N/5)=0 then S:= S+N;
```

return S; ];

func Sum2(D); \Return sum of sequence using N*(N+1)/2 int D; int Q; [Q:= (1000-1)/D; return Q*(Q+1)/2*D; ];

func Sum3(D); \Return sum of sequence for really big number string 0; \don't terminate strings by setting most significant bit int D; \divisor int I; char P(40), Q(40), R(40); \product, quotient, result [StrNDiv("99999999999999999999", D, Q, 20); \Q:= (1E20-1)/D for I:= 0 to 17 do R(I):= ^0; \R:= D R(18):= D/10 +^0; R(19):= rem(0) +^0; StrNMul(Q, R, P, 20); \P:= Q*R = Q*D StrNAdd("00000000000000000001", Q, 20); \Q:= Q+1 StrNMul(P+20, Q, R, 20); \R:= P*Q = Q*D*(Q+1) StrNDiv(R, 2, Q, 40); \Q:= P/2 = Q*D*(Q+1)/2 return Q; \(very temporary location) ];

char S(40), T; [IntOut(0, Sum1); CrLf(0);

```IntOut(0, Sum2(3) + Sum2(5) - Sum2(3*5));  CrLf(0);
```

StrNCopy(Sum3(3), S, 40); StrNAdd(Sum3(5), S, 40); T:= Sum3(3*5); StrNSub(S, T, 40); TextN(0, T, 40); CrLf(0); ]</lang>

Output:
```233168
233168
2333333333333333333316666666666666666668
```