Sum multiples of 3 and 5: Difference between revisions

 

'''Extra credit:''' do this efficiently for ''n'' = 1e20 or higher.

 

{{out}}

<pre>233168</pre>

 

=={{header|AutoHotkey}}==

 

 

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

}

return sum

'''Output:''' <pre>Sum is 233168 for n = 1000

Sum is 233168 for n = 1000</pre>

=={{header|AWK}}==

Save this into file "sum_multiples_of3and5.awk"

{

n = $1-1;

m = int(n/d);

return (d*m*(m+1)/2);

 

{{Out}}

2333333333333333333316666666666666666668</pre>

 

{{works with|FreeBASIC}}

Function mulsum35(n as integer) as integer

Dim s as integer

Print mulsum35(1000)

Sleep

{{out}}

<pre>233168</pre>

=={{header|bc}}==

{{trans|Groovy}}

auto m

 

 

s(1000)

{{Out}}

<pre>233168

2333333333333333333316666666666666666668</pre>

 

Slow (iterative) version:

>+\:v >:5%#v_^

{{Out}}

<pre>233168</pre>

Fast (analytic) version:

{{Out}}

<pre>233168</pre>

 

=={{header|C}}==

===Simple version===

#include <stdlib.h>

 

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

return 0;

{{Out}}

<pre>$ ./a.out

===Fast version with arbitrary precision===

{{libheader|GMP}}

#include <gmp.h>

 

mpz_clear(limit);

return 0;

{{Out}}

<pre>$ ./a.out

The following C# 5 / .Net 4 code is an <i>efficient solution</i> 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 <i>faster</i> to conduct the calculation for smaller values with native ("primitive") types using a 'brute force' iteration approach.

 

using System;

using System.Collections.Generic;

}

}

{{out}}

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

 

=={{header|C++}}==

#include <iostream>

 

return system( "pause" );

}

{{out}}

 

=={{header|Clojure}}==

Quick, concise way:

(let [pred (apply some-fn

(map #(fn [x] (zero? (mod x %))) mults))]

(->> (range n) (filter pred) (reduce +))))

 

Or optimized (translated from Groovy):

(let [n1 (/' (inc' n) f)]

 

(def sum-35 #(-> % (sum-mul 3) (+ (sum-mul % 5)) (- (sum-mul % 15))))

 

=={{header|COBOL}}==

Using OpenCOBOL.

 

Identification division.

Program-id. three-five-sum.

or function mod(ws-the-number, 5) = zero

then add ws-the-number to ws-the-sum.

 

Output:

 

Using triangular numbers:

Identification division.

Program-id. three-five-sum-fast.

Compute ls-ret = ls-fac * ws-n1 * ws-n2 / 2.

goback.

 

Output:

1000000000 = 233333333166666668

</pre>

 

=={{header|Common Lisp}}==

Slow, naive version:

(loop for x below limit

when (or (zerop (rem x 3)) (zerop (rem x 5)))

 

Fast version (adapted translation of [[#Tcl|Tcl]]):

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

 

{{Out}}

> (sum-3-5-fast 1000000000000000000000)

233333333333333333333166666666666666666668</pre>

 

=={{header|Component Pascal}}==

BlackBox Component Builder

MODULE Sum3_5;

IMPORT StdLog, Strings, Args;

 

END Sum3_5.

Execute: ^Q Sum3_5.Compute 1000 ~ <br/>

Output:

<pre>

Sum: 233168

</pre>

 

=={{header|D}}==

 

BigInt sum35(in BigInt n) pure nothrow {

static BigInt sumMul(in BigInt n, in int f) pure nothrow {

return f * n1 * (n1 + 1) / 2;

}

 

void main() {

1000.BigInt.sum35.writeln;

(10.BigInt ^^ 20).sum35.writeln;

{{out}}

2333333333333333333316666666666666666668</pre>

 

 

 

=={{header|Delphi}}==

 

{$APPTYPE CONSOLE}

end;

writeln(sum);

{{out}}

<pre>233168</pre>

 

=={{header|Eiffel}}==

 

class

end

 

{{out}}

<pre>

=={{header|Elixir}}==

Simple (but slow)

 

Fast version:

{{trans|Ruby}}

def sumMul(n, f) do

n1 = div(n - 1, f)

n = round(:math.pow(10, i))

IO.puts RC.sum35(n)

 

{{out}}

 

=={{header|Emacs Lisp}}==

 

 

=={{header|Erlang}}==

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

 

 

{{out}}

 

=={{header|F_Sharp|F#}}==

 

printfn "%d" (sum35 1000)

 

[for i = 0 to 30 do yield i]

{{out}}

<pre style="height:5em">233168

2333333333333333333333333333316666666666666666666666666668

233333333333333333333333333333166666666666666666666666666668</pre>

 

=={{header|FBSL}}==

Derived from BASIC version

 

FUNCTION sumOfThreeFiveMultiples(n AS INTEGER)

PRINT sumOfThreeFiveMultiples(1000)

PAUSE

Output

<pre>233168

 

=={{header|Forth}}==

0 swap

3 do

. ;

 

 

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.

 

 

: >dtriangular ( n -- d )

100000000000000000 2333333333333333316666666666666668

1000000000000000000 233333333333333333166666666666666668 ok

 

=={{header|Go}}==

 

import "fmt"

}

 

{{out}}

<pre>

</pre>

Extra credit:

 

import (

s := sum2(b3)

return s.Rsh(s.Sub(s.Add(s, sum2(b5)), sum2(b15)), 1)

{{out}}

<pre>

 

=={{header|Groovy}}==

Test Code:

println "Checking $arg == $value"

assert sum35(arg) == value

{{out}}

<pre>Checking 1000 == 233168

=={{header|Haskell}}==

Also a method for calculating sum of multiples of any list of numbers.

 

 

pairLCM [] = []

 

sumMulS _ [] = 0

{{out}}

<pre>233168

The following works in both langauges.

 

n := (integer(A[1]) | 1000)-1

write(sum(n,3)+sum(n,5)-sum(n,15))

procedure sum(n,m)

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

 

Sample output:

=={{header|J}}==

 

 

 

 

 

 

 

 

 

=={{header|Java}}==

public static long getSum(long n) {

long sum = 0;

System.out.println(getSum(1000));

}

{{out}}

<pre>233168</pre>

 

=={{header|jq}}==

def sum_multiples(d):

((./d) | floor) | (d * . * (.+1))/2 ;

def task(a;b):

. - 1

 

jq does not (yet) support arbitrary-precision integer arithmetic but converts large integers to floats, so:

1000 | task(3;5) # => 233168

 

 

=={{header|Julia}}==

sum multiples of each, minus multiples of the least common multiple (lcm). Similar to MATLAB's version.

Output:

<pre>julia> multsum(3, 5, 1000)

(100000000000000000000,2333333333333333333316666666666666666668)</pre>

a slightly more efficient version

 

=={{header|Lasso}}==

while(#limit <= 100000) => {^

local(s = 0)

'The sum of multiples of 3 or 5 between 1 and '+(#limit-1)+' is: '+#s+'\r'

#limit = integer(#limit->asString + '0')

{{out}}

<pre>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 9999 is: 23331668

The sum of multiples of 3 or 5 between 1 and 99999 is: 2333316668</pre>

 

=={{header|Limbo}}==

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

 

 

include "sys.m"; sys: Sys;

sub(isum_multiples(ints[15], limit)));

}

 

{{out}}

2333333333333333333316666666666666666668</pre>

 

 

Sum[k, {k, 3, n - 1, 3}] + Sum[k, {k, 5, n - 1, 5}] -

Sum[k, {k, 15, n - 1, 15}]

{{out}}

<pre>233168</pre>

{{out}}

<pre>233333333333333333333166666666666666666668</pre>

Another alternative is

 

=={{header|MATLAB}} / {{header|Octave}}==

<pre>ans = 233168</pre>

Another alternative is

Of course, it's more efficient to use [http://mathforum.org/library/drmath/view/57919.html Gauss' approach] of adding subsequent integers:

n3=floor(n/3);

n5=floor(n/5);

n15=floor(n/15);

<pre>ans = 233168</pre>

 

=={{header|Maxima}}==

 

 

sum35(1000);

Output:

 

=={{header|NetRexx}}==

options replace format comments java crossref symbols nobinary

numeric digits 40

 

-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

method sum_mults(first, limit) public static

last = limit - 1

say

return

{{out}}

<pre>

1000000000000000000000000000|233333333333333333333333333166666666666666666666666668

Elapsed time: 0.005545s

</pre>

 

=={{header|Nim}}==

if x mod 3 == 0 or x mod 5 == 0:

result += x

 

 

 

proc sumMults(first: int32, limit: BigInt): BigInt =

while x < "1000000000000000000000000000000".initBigInt:

echo sum35 x

23

2318

23333333333333333333333333331666666666666666666666666668

2333333333333333333333333333316666666666666666666666666668</pre>

 

=={{header|Oforth}}==

 

 

Output:

<pre>

233168

</pre>

 

{{works with|Free Pascal|2.6.2}}

 

function Multiple(x, y: integer): Boolean;

{ Show sum of all multiples less than 1000. }

writeln(SumMultiples(1000))

 

=={{header|Perl}}==

use List::Util qw( sum ) ;

 

return sum grep { $_ % 3 == 0 || $_ % 5 == 0 } ( 1..$limit - 1 ) ;

}

 

{{Out}}

 

{{Trans|Tcl}}

An alternative approach, using the analytical solution from the Tcl example.

}

 

}

 

use bigint; # Machine precision was sufficient for the first calculation

{{Out}}

<pre>233168

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

 

 

{{out}}

<pre>233168</pre>

}

 

}

 

{{out}}

23

2318

23333333333333333331666666666666666668

2333333333333333333316666666666666666668

 

=={{header|PL/I}}==

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

 

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

 

Outputs:

<pre>

The number of multiples of 3 or 5 below 10000000 is 23333331666668

The number of multiples of 3 or 5 below 100000000 is 2333333316666668</pre>

 

=={{header|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.

{

Param

}

$Sum

{{out}}

<pre>Get-SumOfMultiples</pre>

=={{header|Prolog}}==

===Slow version===

sum_of_multiples_of_3_and_5(N, 1, 0, TT).

 

sum_of_multiples_of_3_and_5(N, K1, C5, S).

 

 

===Fast version===

maplist(compute_sum(N), [3,5,15], [TT3, TT5, TT15]),

TT is TT3 + TT5 - TT15.

; N2 is N div N1),

Sum is N1 * N2 * (N2 + 1) / 2.

 

Output :

TT = 2333333333333333333316666666666666666668.

</pre>

=={{header|Python}}==

Three ways of performing the calculation are shown including direct calculation of the value without having to do explicit sums in sum35c()

'Direct count'

# note: ranges go to n-1

# Scalability

p = 20

 

{{out}}

 

For n = 100000000000000000000 -> 2333333333333333333316666666666666666668</pre>

 

=={{header|R}}==

 

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

 

=={{header|Racket}}==

#lang racket

(require math)

 

(for/list ([k 20]) (analytical k))

Output:

'(0 23 2318 233168 23331668 2333316668 233333166668)

'(0

233333333333333333166666666666666668

23333333333333333331666666666666666668)

 

=={{header|REXX}}==

===version 1===

* 14.05.2013 Walter Pachl

**********************************************************************/

s=s+i

End

Output:

<pre>233168</pre>

 

===version 2===

* 15.05.2013 Walter Pachl

**********************************************************************/

last = last - last // first

sum = (last % first) * (first + last) % 2

Output:

<pre> 1 0

 

===version 3===

<pre>

 

</pre>

 

</pre>

 

=={{header|Ruby}}==

Simple Version (Slow):

end

 

Fast Version:

#

# Nigel_Galloway

 

# For extra credit

 

{{out}}

Other way:

{{trans|D}}

n1 = (n - 1) / f

f * n1 * (n1 + 1) / 2

for i in 1..20

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

 

{{out}}

 

=={{header|Run BASIC}}==

end

function multSum35(n)

If (i mod 3 = 0) or (i mod 5 = 0) then multSum35 = multSum35 + i

next i

 

=={{header|Scala}}==

 

// Simplest solution but limited to Ints only

{

for( i <- (0 to 20); n = "1"+"0"*i ) println( (" " * (21 - i)) + n + " => " + (" " * (21 - i)) + sum35(BigInt(n)) )

{{out}}

<pre> 1 => 0

 

=={{header|Scheme}}==

 

Output:

Or, more clearly by decomposition:

 

(or (zero? (remainder x 3))

(zero? (remainder x 5))))

(+ tot (if (fac35? x) x 0)))

 

 

Output:

For larger numbers iota can take quite a while just to build the list -- forget about waiting for all the computation to finish!

 

(let* ((n1 (quotient (- n 1) fac))

(n2 (+ n1 1)))

(fast35sum 1000)

(fast35sum 100000000000000000000)

 

Output:

 

=={{header|Seed7}}==

include "bigint.s7i";

 

writeln(sum35(1000_));

writeln(sum35(10_ ** 20));

 

{{out}}

=={{header|Sidef}}==

{{trans|Ruby}}

}

 

func sum35(n) {

}

 

{{out}}

<pre>

20: 100000000000000000000 2333333333333333333316666666666666666668

</pre>

 

=={{header|Tcl}}==

proc mul35sum {n} {

for {set total [set threes [set fives 0]]} {$threes<$n||$fives<$n} {} {

}

return $total

However, that's pretty dumb. We can do much better by observing that the sum of the multiples of <math>k</math> below some <math>n+1</math> is <math>k T_{n/k}</math>, where <math>T_i</math> is the <math>i</math>'th [[wp:Triangular number|triangular number]], for which there exists a trivial formula. Then we simply use an overall formula of <math>3T_{n/3} + 5T_{n/5} - 15T_{n/15}</math> (that is, summing the multiples of three and the multiples of five, and then subtracting the multiples of 15 which were double-counted).

proc tcl::mathfunc::triangle {n} {expr {

$n * ($n+1) / 2

incr n -1

expr {3*triangle($n/3) + 5*triangle($n/5) - 15*triangle($n/15)}

Demonstrating:

puts [mul35sum 10000000],[sum35 10000000]

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

{{out}}

<pre>233168,233168

23333331666668,23333331666668

2333333333333333333316666666666666666668