Rosetta Code

Sum multiples of 3 and 5

Revision as of 22:11, 12 November 2013 by rosettacode>Trap D (→‎Slow version)

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.

Task
Sum multiples of 3 and 5
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.

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 });
           candidates.Add(BigInteger.Parse("100000000000000000000"));

           foreach (BigInteger candidate in candidates)
           {
               BigInteger c = candidate - 1;
               BigInteger answer3 = GetSumOfNumbersDivisibleByN(c, 3);
               BigInteger answer5 = GetSumOfNumbersDivisibleByN(c, 5);
               BigInteger answer15 = GetSumOfNumbersDivisibleByN(c, 15);

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

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

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>

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

Haskell

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

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
  3. Nigel_Galloway
  4. 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   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

}}

  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

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
Retrieved from "https://rosettacode.org/wiki/Sum_multiples_of_3_and_5?oldid=231714"