Sum multiples of 3 and 5: Difference between revisions

From Rosetta Code
Content added Content deleted
Line 864: Line 864:


=={{header|Julia}}==
=={{header|Julia}}==
sum multiples of each, minus multiples of the least common multiple (lcm).
sum multiples of each, minus multiples of the least common multiple (lcm). Similar to MATLAB's version.
<lang Julia>multsum(n, m, lim) = sum(0:n:lim-1) + sum(0:m:lim-1) - sum(0:lcm(n,m):lim-1)</lang>
<lang Julia>multsum(n, m, lim) = sum(0:n:lim-1) + sum(0:m:lim-1) - sum(0:lcm(n,m):lim-1)</lang>
Output:
Output:
Line 900: Line 900:
(10000000000000000000,23333333333333333331666666666666666668)
(10000000000000000000,23333333333333333331666666666666666668)
(100000000000000000000,2333333333333333333316666666666666666668)</pre>
(100000000000000000000,2333333333333333333316666666666666666668)</pre>
a slightly more efficient version
<lang Julia>multsum(n, lim) = (occ = div(lim-1, n); div(n*occ*(occ+1), 2))
multsum(n, m, lim) = multsum(n,lim) + multsum(m,lim) - multsum(lcm(n,m),lim)</lang>


=={{header|Lasso}}==
=={{header|Lasso}}==

Revision as of 00:08, 24 June 2014

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.

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

AutoHotkey

<lang AutoHotkey>n := 1000

msgbox % "Sum is " . Sum3_5(n) . " for n = " . n msgbox % "Sum is " . Sum3_5_b(n) . " for n = " . n

Standard simple Implementation.

Sum3_5(n) { sum := 0 loop % n-1 { if (!Mod(a_index,3) || !Mod(a_index,5)) sum:=sum+A_index } return sum }

Translated from the C++ version.

Sum3_5_b( i ) { sum := 0, a := 0 while (a < 28) { if (!Mod(a,3) || !Mod(a,5)) { sum += a s := 30 while (s < i) { if (a+s < i) sum += (a+s) s+=30 } } a+=1 } return sum }</lang>

Output: 

Sum is 233168 for n = 1000
Sum is 233168 for n = 1000

AWK

Save this into file "sum_multiples_of3and5.awk" <lang AWK>#!/usr/bin/awk -f { n = $1-1; print 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:
$ echo 1000 |awk -f sum_multiples_of3and5.awk 
233168

Extra credit

Works with: Gawk version 4.1

In Awk, all numbers are represented internally as double precision floating-point numbers. Thus the result for the extra credit is unprecise. Since version 4.1, GNU Awk supports high precision arithmetic (using GNU MPFR and GMP) which is turned on with the -M / --bignum option. The variable PREC sets the working precision for arithmetic operations (here 80 bits): 

$ echo -e "1000\n1e20" | gawk -M -v PREC=80 -f sum_multiples_of3and5.awk 
233168
2333333333333333333316666666666666666668

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

bc

Translation of: Groovy

<lang bc>define t(n, f) { 

   auto m

   m = (n - 1) / f
   return(f * m * (m + 1) / 2)

}

define s(l) { 

   return(t(l, 3) + t(l, 5) - t(l, 15))

}

s(1000) s(10 ^ 20)</lang>

Output:
233168
2333333333333333333316666666666666666668

C

Simple version

<lang c>#include <stdio.h>

  1. include <stdlib.h>

unsigned long long sum35(unsigned long long limit) { 

   unsigned long long sum = 0;
   for (unsigned long long i = 0; i < limit; i++)
       if (!(i % 3) || !(i % 5))
           sum += i;
   return sum;

}

int main(int argc, char **argv) { 

   unsigned long long limit;

   if (argc == 2)
       limit = strtoull(argv[1], NULL, 10);
   else
       limit = 1000;

   printf("%lld\n", sum35(limit));
   return 0;

}</lang>

Output:
$ ./a.out
233168
$ ./a.out 12345
35553600

Fast version with arbitrary precision

Library: GMP

<lang c>#include <stdio.h>

  1. include <gmp.h>

void sum_multiples(mpz_t result, const mpz_t limit, const unsigned f) { 

   mpz_t m;
   mpz_init(m);
   mpz_sub_ui(m, limit, 1);
   mpz_fdiv_q_ui(m, m, f);

   mpz_init_set(result, m);
   mpz_add_ui(result, result, 1);
   mpz_mul(result, result, m);
   mpz_mul_ui(result, result, f);
   mpz_fdiv_q_2exp(result, result, 1);

   mpz_clear(m);

}

int main(int argc, char **argv) { 

   mpf_t temp;
   mpz_t limit;

   if (argc == 2)
   {
       mpf_init_set_str(temp, argv[1], 10);
       mpz_init(limit);
       mpz_set_f(limit, temp);
       mpf_clear(temp);
   }
   else
       mpz_init_set_str(limit, "1000000000000000000000", 10);

   mpz_t temp_sum;
   mpz_t sum35;
   
   mpz_init(temp_sum);
   sum_multiples(temp_sum, limit, 3);
   mpz_init_set(sum35, temp_sum);
   sum_multiples(temp_sum, limit, 5);
   mpz_add(sum35, sum35, temp_sum);
   sum_multiples(temp_sum, limit, 15);
   mpz_sub(sum35, sum35, temp_sum);

   mpz_out_str(stdout, 10, sum35);
   puts("");

   mpz_clear(temp_sum);
   mpz_clear(sum35);
   mpz_clear(limit);
   return 0;

}</lang>

Output:
$ ./a.out 
233333333333333333333166666666666666666668
$ ./a.out 23e45
123433333333333333333333333333333333333333333314166666666666666666666666666666666666666666668

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

Quick, concise way: <lang clojure>(defn sum-mults [n & mults] 

 (let [pred (apply some-fn
              (map #(fn [x] (zero? (mod x %))) mults))]
   (->> (range n) (filter pred) (reduce +))))

(println (sum-mults 1000 3 5))</lang> Or optimized (translated from Groovy): <lang clojure>(defn sum-mul [n f] 

 (let [n1 (/' (inc' n) f)]
   (*' f n1 (inc' n1) 1/2)

(def sum-35 #(-> % (sum-mul 3) (+ (sum-mul % 5)) (- (sum-mul % 15)))) (println (sum-35 1000000000))</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

Common Lisp

Slow, naive version: <lang lisp>(defun sum-3-5-slow (limit) 

 (loop for x below limit
       when (or (zerop (rem x 3)) (zerop (rem x 5)))
         sum x))</lang>

Fast version (adapted translation of Tcl): <lang lisp>(defun sum-3-5-fast (limit) 

 (flet ((triangular (n) (truncate (* n (1+ n)) 2)))
   (let ((n (1- limit)))  ; Sum multiples *below* the limit
     (- (+ (* 3 (triangular (truncate n 3))) 
           (* 5 (triangular (truncate n 5)))) 
        (* 15 (triangular (truncate n 15)))))))</lang>
Output:
> (values (sum-3-5-slow 1000) (sum-3-5-fast 1000))
233168 ;
233168
> (sum-3-5-fast 1000000000000000000000)
233333333333333333333166666666666666666668


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

Delphi

<lang delphi>program sum35;

{$APPTYPE CONSOLE}

var 

 sum: integer;
 i: integer;

function isMultipleOf(aNumber, aDivisor: integer): boolean; begin 

 result := aNumber mod aDivisor = 0

end;

begin 

 sum := 0;
 for i := 3 to 999 do
 begin
   if isMultipleOf(i, 3) or isMultipleOf(i, 5) then
     sum := sum + i;
 end;
 writeln(sum);

end.</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>

Go

<lang go>package main

import "fmt"

func main() { 

   fmt.Println(s35(1000))

}

func s35(i int) int { 

   i--
   sum2 := func(d int) int {
       n := i / d
       return d * n * (n + 1)
   }
   return (sum2(3) + sum2(5) - sum2(15)) / 2

}</lang>

Output:
233168

Extra credit: <lang go>package main

import ( 

   "fmt"
   "math/big"

)

var ( 

   b1  = big.NewInt(1)
   b3  = big.NewInt(3)
   b5  = big.NewInt(5)
   b10 = big.NewInt(10)
   b15 = big.NewInt(15)
   b20 = big.NewInt(20)

)

func main() { 

   fmt.Println(s35(new(big.Int).Exp(b10, b3, nil)))
   fmt.Println(s35(new(big.Int).Exp(b10, b20, nil)))

}

func s35(i *big.Int) *big.Int { 

   j := new(big.Int).Sub(i, b1)
   sum2 := func(d *big.Int) *big.Int {
       n := new(big.Int).Quo(j, d)
       p := new(big.Int).Add(n, b1)
       return p.Mul(d, p.Mul(p, n))
   }
   s := sum2(b3)
   return s.Rsh(s.Sub(s.Add(s, sum2(b5)), sum2(b15)), 1)

}</lang>

Output:
233168
2333333333333333333316666666666666666668

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

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

Julia

sum multiples of each, minus multiples of the least common multiple (lcm). Similar to MATLAB's version. <lang Julia>multsum(n, m, lim) = sum(0:n:lim-1) + sum(0:m:lim-1) - sum(0:lcm(n,m):lim-1)</lang> Output: 

julia> multsum(3, 5, 1000)
233168

julia> multsum(3, 5, BigInt(10)^20)
2333333333333333333316666666666666666668

julia> @time multsum(3, 5, BigInt(10)^20)
elapsed time: 5.8114e-5 seconds seconds (3968 bytes allocated)
2333333333333333333316666666666666666668

julia> [(BigInt(10)^n, multsum(3, 5, BigInt(10)^n)) for n=0:20]
21-element Array{(BigInt,BigInt),1}:
 (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)

a slightly more efficient version <lang Julia>multsum(n, lim) = (occ = div(lim-1, n); div(n*occ*(occ+1), 2)) multsum(n, m, lim) = multsum(n,lim) + multsum(m,lim) - multsum(lcm(n,m),lim)</lang>

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

Maple

By using symbolic function sum instead of numeric function add the program F will run O(1) rather than O(n). <lang Maple> F := unapply( sum(3*i,i=1..floor((n-1)/3)) 

            + sum(5*i,i=1..floor((n-1)/5))
            - sum(15*i,i=1..floor((n-1)/15)), n);

F(1000);

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

                               2                                      2
               3      /1     2\    3      /1     2\   5      /1     4\ 
     F := n -> - floor|- n + -|  - - floor|- n + -| + - floor|- n + -| 
               2      \3     3/    2      \3     3/   2      \5     5/ 

                                                2                      
          5      /1     4\   15      /1      14\    15      /1      14\
        - - floor|- n + -| - -- floor|-- n + --|  + -- floor|-- n + --|
          2      \5     5/   2       \15     15/    2       \15     15/


                                   233168

                  2333333333333333333316666666666666666668

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

<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, it's more efficient to use Gauss' approach of adding subsequent integers: <lang MATLAB>n=999; 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 =  233168

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 = 233168
%2 = 2333333333333333333316666666666666666668

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 !
Translation of: Tcl

An alternative approach, using the analytical solution from the Tcl example. <lang Perl>sub tri { 

   my $n = shift;
   return $n*($n+1) / 2;

}

sub sum { 

   my $n = (shift) - 1;
   return (3 * tri($n / 3) + 5 * tri($n / 5) - 15 * tri($n / 15));

}

say sum(1e3); use bigint; # Machine precision was sufficient for the first calculation say sum(1e20);</lang>

Output:
233168
2333333333333333333316666666666666666668

Interestingly, the prime factorization of the second result produces a 35 digit prime number.

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

PL/I

<lang PL/I>threeor5: procedure options (main); /* 8 June 2014 */ 

  declare (i, n) fixed(10), sum fixed (31) static initial (0);

  get (n);
  put ('The number of multiples of 3 or 5 below ' || trim(n) || ' is');

  do i = 1 to n-1;
     if mod(i, 3) = 0 | mod(i, 5) = 0 then sum = sum + i;
  end;

  put edit ( trim(sum) ) (A);

end threeor5;</lang> Outputs: 

The number of multiples of 3 or 5 below 1000 is 233168
The number of multiples of 3 or 5 below 10000 is 23331668
The number of multiples of 3 or 5 below 100000 is 2333316668
The number of multiples of 3 or 5 below 1000000 is 233333166668
The number of multiples of 3 or 5 below 10000000 is 23333331666668
The number of multiples of 3 or 5 below 100000000 is 2333333316666668

PowerShell

Here is a cmdlet 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

Simple Version (Slow): <lang ruby>def sum35(n) 

 (1...n).select{|i|i%3==0 or i%5==0}.inject(:+)

end puts sum35(1000) #=> 233168</lang>

Fast Version: <lang ruby># 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

puts g(3,5,999)

  1. For extra credit

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

Output:
233168
2333333333333333333316666666666666666668

Other way:

Translation of: D

<lang ruby>def sumMul(n, f) 

 n1 = (n - 1) / f
 f * n1 * (n1 + 1) / 2

end

def sum35(n) 

 sumMul(n, 3) + sumMul(n, 5) - sumMul(n, 15)

end

for i in 1..20 

 puts "%2d:%22d %s" % [i, 10**i, sum35(10**i)]

end</lang>

Output:
 1:                    10 23
 2:                   100 2318
 3:                  1000 233168
 4:                 10000 23331668
 5:                100000 2333316668
 6:               1000000 233333166668
 7:              10000000 23333331666668
 8:             100000000 2333333316666668
 9:            1000000000 233333333166666668
10:           10000000000 23333333331666666668
11:          100000000000 2333333333316666666668
12:         1000000000000 233333333333166666666668
13:        10000000000000 23333333333331666666666668
14:       100000000000000 2333333333333316666666666668
15:      1000000000000000 233333333333333166666666666668
16:     10000000000000000 23333333333333331666666666666668
17:    100000000000000000 2333333333333333316666666666666668
18:   1000000000000000000 233333333333333333166666666666666668
19:  10000000000000000000 23333333333333333331666666666666666668
20: 100000000000000000000 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} { 

   incr n -1
   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:
233168,233168
23333331666668,23333331666668
2333333333333333333316666666666666666668

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

zkl

Brute force: <lang zkl>[3..999,3].reduce('+,0) + [5..999,5].reduce('+,0) - [15..999,15].reduce('+,0) 233168</lang>

Translation of: Groovy

Using a formula, making sure the input will cast the result to the same type (ie if called with a BigNum, the result is a BigNum). <lang zkl>fcn sumMul(N,m){N=(N-1)/m; N*(N+1)*m/2} fcn sum35(N){sumMul(N,3) + sumMul(N,5) - sumMul(N,15)}</lang>

Output:
zkl: sum35(1000)  // int-->int
233168

zkl: var BN=Import("zklBigNum");
zkl: sum35(BN("1"+"0"*21))  // 1 with 21 zeros, BigNum-->BigNum
233333333333333333333166666666666666666668
sum35(BN("1"+"0"*15)) : "%,d".fmt(_)// 1e15, BigNum don't like float format input
233,333,333,333,333,166,666,666,666,668
Retrieved from "https://rosettacode.org/wiki/Sum_multiples_of_3_and_5?oldid=231756"