Sum multiples of 3 and 5: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|J}}) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 12:
=={{header|11l}}==
<
V sum = 0
L(i) 1 .< limit
Line 19:
R sum
print(sum35(1000))</
{{out}}
Line 28:
=={{header|8th}}==
Implements both the naive method and inclusion/exclusion.
<
needs combinators/bi
Line 51:
"For 10^20 - 1, the sum is " . 10 20 ^ 1- sumdiv_3,5 . cr
bye
</syntaxhighlight>
{{Out}}
<pre>
Line 58:
</pre>
=={{header|360 Assembly}}==
<
SUM35 CSECT
USING SUM35,R13 base register
Line 103:
PG DC CL80'123456789012 : 1234567890123456'
YREGS
END SUM35</
{{out}}
<pre>
Line 117:
=={{header|Action!}}==
{{libheader|Action! Tool Kit}}
<
PROC Main()
Line 134:
PrintRE(sum)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Sum_multiples_of_3_and_5.png Screenshot from Atari 8-bit computer]
Line 142:
=={{header|Ada}}==
<
procedure Sum_Multiples is
Line 162:
Ada.Text_IO.Put_Line ("n=1000: " & Sum_3_5 (1000)'Image);
Ada.Text_IO.Put_Line ("n=5e9 : " & Sum_3_5 (5e9)'Image);
end Sum_Multiples;</
{{out}}
<pre>n=1000: 233168
Line 169:
===Extra Credit===
Requires upcoming Ada 202x with big integer package.
<
with Ada.Numerics.Big_Numbers.Big_Integers;
Line 207:
end;
end loop;
end Sum_Multiples_Big;</
{{out}}
<pre> n : Sum_35 (n)
Line 246:
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Uses Algol 68G's LONG LONG INT to handle large numbers.
<
PROC sum of multiples of 3 and 5 below = ( LONG LONG INT n )LONG LONG INT:
BEGIN
Line 271:
, newline
)
)</
{{out}}
<pre>
Line 280:
=={{header|APL}}==
=== Dyalog APL ===
<
Sum ← +/∘⍸1<15∨⍳
</syntaxhighlight>
{{out}}
<pre> Sum 999
Line 288:
=== ngn/APL ===
<
{+/((0=3|a)∨0=5|a)/a←⍳⍵} 1000</
{{out}}
<pre>233168</pre>
Line 295:
=={{header|AppleScript}}==
{{Trans|JavaScript}}
<
-- sum35 :: Int -> Int
Line 372:
end script
end if
end mReturn</
{{Out}}
10<sup>1</sup> -> 23<br>10<sup>2</sup> -> 2318<br>10<sup>3</sup> -> 233168<br>10<sup>4</sup> -> 23331668<br>10<sup>5</sup> -> 2.333316668E+9<br>10<sup>6</sup> -> 2.33333166668E+11<br>10<sup>7</sup> -> 2.333333166667E+13<br>10<sup>8</sup> -> 2.333333316667E+15<br>
Line 378:
=={{header|Arturo}}==
<
sum select 1..n-1 [x][or? 0=x%3 0=x%5]
]
print sumMul35 1000</
{{out}}
Line 390:
=={{header|AutoHotkey}}==
<
msgbox % "Sum is " . Sum3_5(n) . " for n = " . n
Line 424:
}
return sum
}</
'''Output:''' <pre>Sum is 233168 for n = 1000
Sum is 233168 for n = 1000</pre>
Line 430:
=={{header|AWK}}==
Save this into file "sum_multiples_of3and5.awk"
<
{
n = $1-1;
Line 438:
m = int(n/d);
return (d*m*(m+1)/2);
}</
{{Out}}
Line 454:
=={{header|BASIC}}==
{{works with|FreeBASIC}}
<
Function mulsum35(n as integer) as integer
Dim s as integer
Line 466:
Print mulsum35(1000)
Sleep
End</
{{out}}
<pre>233168</pre>
==={{header|BASIC256}}===
<
if n = 0 then return 0
suma = 0
Line 481:
print multSum35(999)
end</
==={{header|QBasic}}===
<
IF n = 0 THEN multSum35 = 0
suma = 0
Line 493:
END FUNCTION
PRINT multSum35(999)</
==={{header|True BASIC}}===
<
IF n = 0 THEN LET multSum35 = 0
LET suma = 0
Line 506:
PRINT multSum35(999)
END</
==={{header|Yabasic}}===
<
if n = 0 then return 0 : fi
suma = 0
Line 519:
print multSum35(999)
end</
==={{header|IS-BASIC}}===
<
110 DEF MULTSUM35(N)
120 LET S=0
Line 529:
150 NEXT
160 LET MULTSUM35=S
170 END DEF</
==={{header|Sinclair ZX81 BASIC}}===
Line 535:
The ZX81 doesn't offer enough numeric precision to try for the extra credit. This program is pretty unsophisticated; the only optimization is that we skip testing whether <math>i</math> is divisible by 5 if we already know it's divisible by 3. (ZX81 BASIC doesn't do this automatically: both sides of an <code>OR</code> are evaluated, even if we don't need the second one.) Even so, with <math>n</math> = 1000 the performance is pretty acceptable.
<
20 FAST
30 LET SUM=0
Line 544:
80 NEXT I
90 SLOW
100 PRINT SUM</
{{in}}
<pre>1000</pre>
Line 552:
=={{header|bc}}==
{{trans|Groovy}}
<
auto m
Line 564:
s(1000)
s(10 ^ 20)</
{{Out}}
<pre>233168
Line 571:
=={{header|BCPL}}==
There is both the naive method and the fast inclusion/exclusion method demonstrated. The code is limited to values that don't overflow a 64 bit integer.
<syntaxhighlight lang="bcpl">
GET "libhdr"
Line 597:
RESULTIS 0
}
</syntaxhighlight>
{{Out}}
<pre>
Line 616:
=={{header|Befunge}}==
Slow (iterative) version:
<
>+\:v >:5%#v_^
@.$_^#! < > ^</
{{Out}}
<pre>233168</pre>
Fast (analytic) version:
<
{{Out}}
<pre>233168</pre>
Line 628:
=={{header|BQN}}==
A naive solution:
<
A much faster solution:
<
m ← (0=3⊸|⌊5⊸|)↕15 ⋄ h‿l ← 15(⌊∘÷˜∾|)𝕩
(+´l↑m×15(×+↕∘⊣)h) + (15×(+´m)×2÷˜h×h-1) + h×+´m×↕15
}</
{{out}}
Line 647:
=={{header|C}}==
===Simple version===
<
#include <stdlib.h>
Line 670:
printf("%lld\n", sum35(limit));
return 0;
}</
{{Out}}
<pre>$ ./a.out
Line 679:
===Fast version with arbitrary precision===
{{libheader|GMP}}
<
#include <gmp.h>
Line 731:
mpz_clear(limit);
return 0;
}</
{{Out}}
<pre>$ ./a.out
Line 741:
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;
Line 782:
}
}
</syntaxhighlight>
{{out}}
The sum of numbers divisible by 3 or 5 between 1 and 999 is 233168
Line 797:
=={{header|C++}}==
<
#include <iostream>
Line 840:
return system( "pause" );
}
</syntaxhighlight>
{{out}}
<pre>
Line 848:
===Fast version with arbitrary precision===
{{libheader|Boost}}
<
#include <boost/multiprecision/cpp_int.hpp>
Line 867:
std::cout << sum35(1000) << '\n';
std::cout << sum35(big_int("100000000000000000000")) << '\n';
}</
{{out}}
Line 877:
=={{header|Clojure}}==
Quick, concise way:
<
(let [pred (apply some-fn
(map #(fn [x] (zero? (mod x %))) mults))]
(->> (range n) (filter pred) (reduce +))))
(println (sum-mults 1000 3 5))</
Transducers approach:
<
(transduce (filter (fn [x] (some (fn [mult] (zero? (mod x mult))) mults)))
+ (range n)))
(println (sum-mults 1000 3 5))</
Or optimized (translated from Groovy):
<
(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))</
=={{header|COBOL}}==
Line 903:
Using OpenCOBOL.
<
Identification division.
Program-id. three-five-sum.
Line 927:
or function mod(ws-the-number, 5) = zero
then add ws-the-number to ws-the-sum.
</syntaxhighlight>
Output:
Line 935:
Using triangular numbers:
<
Identification division.
Program-id. three-five-sum-fast.
Line 983:
Compute ls-ret = ls-fac * ws-n1 * ws-n2 / 2.
goback.
</syntaxhighlight>
Output:
Line 993:
A brute-method using only comparisons and adds. Compiles and runs as is in GnuCOBOL 2.0 and Micro Focus Visual COBOL 2.3. Takes about 7.3 seconds to calculate 1,000,000,000 iterations (AMD A6 quadcore 64bit)
<
IDENTIFICATION DIVISION.
PROGRAM-ID. SUM35.
Line 1,034:
EXIT.
END PROGRAM SUM35.
</syntaxhighlight>
Output
<pre>+00233333333166666668</pre>
Line 1,040:
=={{header|Common Lisp}}==
Slow, naive version:
<
(loop for x below limit
when (or (zerop (rem x 3)) (zerop (rem x 5)))
sum x))</
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))))
(* 15 (triangular (truncate n 15)))))))</
{{Out}}
Line 1,062:
=={{header|Component Pascal}}==
BlackBox Component Builder
<
MODULE Sum3_5;
IMPORT StdLog, Strings, Args;
Line 1,089:
END Sum3_5.
</syntaxhighlight>
Execute: ^Q Sum3_5.Compute 1000 ~ <br/>
Output:
Line 1,097:
=={{header|Cowgol}}==
<
# sum multiples up to given input
Line 1,125:
print("Naive method: "); print_i32(sum35(1000, naiveSumMulTo)); print_nl();
print("Fast method: "); print_i32(sum35(1000, fastSumMulTo)); print_nl();
</syntaxhighlight>
{{out}}
Line 1,135:
{{trans|Ruby}}
Short, but not optimized.
<
(0...n).select { |i| i % 3 == 0 || i % 5 == 0 }.sum
end
puts sum_3_5_multiples(1000)</
{{out}}
<pre>
Line 1,149:
To conform to task requirements, and other versions,
modified to find sums below n.
<
def g(n1, n2, n3)
Line 1,161:
# For extra credit
puts g(3,5,"100000000000000000000".to_big_i - 1)
puts g(3,5,"100000000000000000000".to_big_i)</
{{out}}
<pre>
Line 1,171:
Alternative faster version 2.
<
def sumMul(n, f)
Line 1,184:
(1..20).each do |e| limit = 10.to_big_i ** e
puts "%2d:%22d %s" % [e, limit, sum35(limit)]
end</
{{out}}
<pre>
Line 1,210:
=={{header|D}}==
<
BigInt sum35(in BigInt n) pure nothrow {
Line 1,227:
1000.BigInt.sum35.writeln;
(10.BigInt ^^ 20).sum35.writeln;
}</
{{out}}
<pre>
Line 1,237:
=={{header|dc}}==
<
[ d d d 3 r lmx r 5 r lmx + r 15 r lmx - ]ss
Line 1,245:
[ ll p lsx lux p ll 10 * d sl 1000000000000000000000 >d]sd
1 sl ldx</
{{Out}}
Line 1,270:
100000000000000000000 2333333333333333333316666666666666666668</pre>
=={{header|Delphi}}==
<
{$APPTYPE CONSOLE}
Line 1,291:
end;
writeln(sum);
end.</
{{out}}
<pre>233168</pre>
=={{header|Déjà Vu}}==
<
0
for i range 1 -- n:
Line 1,302:
+ i
!. sum-divisible 1000</
{{out}}
<pre>233168</pre>
=={{header|EchoLisp}}==
<
(lib 'math) ;; divides?
(lib 'sequences) ;; sum/when
Line 1,341:
❌ error: expected coprimes (42 666)
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
Line 1,373:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,381:
=={{header|Elixir}}==
Simple (but slow)
<
233168</
Fast version:
{{trans|Ruby}}
<
def sumMul(n, f) do
n1 = div(n - 1, f)
Line 1,400:
n = round(:math.pow(10, i))
IO.puts RC.sum35(n)
end)</
{{out}}
Line 1,430:
Vanilla:
<
(let ((sum 0))
(dotimes (x n)
(when (or (zerop (% x 3)) (zerop (% x 5)))
(setq sum (+ sum x))))
sum))</
{{libheader|seq.el}}
<
(apply #'+ (seq-filter
(lambda (x) (or (zerop (% x 3) ) (zerop (% x 5))))
(number-sequence 1 (- n 1)))))</
=={{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 ->
Line 1,451:
sum_3_5(X-1, Total).
io:format("~B~n", [sum_3_5(1000)]).</
{{out}}
Line 1,457:
=={{header|F_Sharp|F#}}==
<
let sum35 n = Seq.init n (id) |> Seq.reduce (fun sum i -> if i % 3 = 0 || i % 5 = 0 then sum + i else sum)
Line 1,470:
[for i = 0 to 30 do yield i]
|> List.iter (fun i -> printfn "%A" (sum35fast (bigint.Pow(10I, i))))</
{{out}}
<pre style="height:5em">233168
Line 1,515:
<br>
{{works with|Factor|0.99 2019-10-06}}
<
: sum-multiples ( m n upto -- sum )
Line 1,523:
3 5 1000 sum-multiples .
3 5 1e20 sum-multiples .</
{{out}}
<pre>
Line 1,532:
=={{header|FBSL}}==
Derived from BASIC version
<
FUNCTION sumOfThreeFiveMultiples(n AS INTEGER)
Line 1,546:
PRINT sumOfThreeFiveMultiples(1000)
PAUSE
</syntaxhighlight>
Output
<pre>233168
Line 1,554:
=={{header|Forth}}==
<
0 swap
3 do
Line 1,565:
. ;
1000 main \ 233168 ok</
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 )
Line 1,611:
100000000000000000 2333333333333333316666666666666668
1000000000000000000 233333333333333333166666666666666668 ok
</syntaxhighlight>
=={{header|Fortran}}==
Line 1,617:
Early Fortrans did not offer such monsters as INTEGER*8 but the F95 compiler I have does so. Even so, the source is in the style of F77 which means that in the absence of the MODULE protocol, the types of the functions must be specified if they are not default types. F77 also does not accept the <code>END FUNCTION ''name''</code> protocol that F90 does, but such documentation enables compiler checks and not using it makes me wince.
<syntaxhighlight lang="fortran">
INTEGER*8 FUNCTION SUMI(N) !Sums the integers 1 to N inclusive.
Calculates as per the young Gauss: N*(N + 1)/2 = 1 + 2 + 3 + ... + N.
Line 1,657:
GO TO 10 !Have another go.
END !So much for that.
</syntaxhighlight>
Sample output:
<pre>
Line 1,680:
=={{header|FreeBASIC}}==
<
Function sum35 (n As UInteger) As UInteger
Line 1,694:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 1,703:
=={{header|Frink}}==
Program has a brute-force approach for n=1000, and also inclusion/exclusion for larger values.
<syntaxhighlight lang="frink">
sum999 = sum[select[1 to 999, {|n| n mod 3 == 0 or n mod 5 == 0}]]
Line 1,716:
println["The sum of all the multiples of 3 or 5 below 1000 is $sum999"]
println["The sum of all multiples less than 1e20 is " + sum35big[1_00000_00000_00000_00000 - 1]]
</syntaxhighlight>
{{Out}}
<pre>
Line 1,724:
=={{header|Go}}==
<
import "fmt"
Line 1,745:
return n
}</
{{out}}
<pre>
Line 1,751:
</pre>
Extra credit:
<
import (
Line 1,781:
s := sum2(b3)
return s.Rsh(s.Sub(s.Add(s, sum2(b5)), sum2(b15)), 1)
}</
{{out}}
<pre>
Line 1,789:
=={{header|Groovy}}==
<
def sum35 = { sumMul(it, 3) + sumMul(it, 5) - sumMul(it, 15) }</
Test Code:
<
println "Checking $arg == $value"
assert sum35(arg) == value
}</
{{out}}
<pre>Checking 1000 == 233168
Line 1,802:
=={{header|Haskell}}==
Also a method for calculating sum of multiples of any list of numbers.
<
----------------- SUM MULTIPLES OF 3 AND 5 ---------------
Line 1,843:
where
f = sumMul n
g = sumMulS n</
{{out}}
<pre>233168
Line 1,854:
The following works in both langauges.
<
n := (integer(A[1]) | 1000)-1
write(sum(n,3)+sum(n,5)-sum(n,15))
Line 1,861:
procedure sum(n,m)
return m*((n/m)*(n/m+1)/2)
end</
Sample output:
Line 1,876:
The problem can also be solved with a simple use of inclusion/exclusion; this solution is more in keeping with how one could approach the problem from a more traditional language.
<syntaxhighlight lang="j">
NB. Naive method
NB. joins two lists of the multiples of 3 and 5, then uses the ~. operator to remove duplicates.
Line 1,895:
echo 'For 10^20 - 1, the sum is ', ": +/ (".(20#'9'),'x') sumdiv 3 5 _15
</syntaxhighlight>
{{Out}}
<pre>
Line 1,905:
=={{header|Java}}==
===Simple Version===
<
public static long getSum(long n) {
long sum = 0;
Line 1,916:
System.out.println(getSum(1000));
}
}</
{{out}}
<pre>233168</pre>
===Extra Credit===
<syntaxhighlight lang="java">
import java.math.BigInteger;
Line 1,961:
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,995:
===ES5===
JavaScript is better equipped for flexibility than for scale. The value of <syntaxhighlight lang
As ''Number.MAX_SAFE_INTEGER < 1E20'' evaluates to ''true'', the most obvious JS attack on a solution for 1E20 might involve some string processing …
Line 2,001:
At more modest scales, however, we can generalise a little to allow for an arbitrary list of integer factors, and write a simple generate, filter and sum approach:
<
// [n] -> n -> n
Line 2,059:
JSON.stringify(lstTable);
})([3, 5], 8);</
Line 2,085:
|}
<
["10^4",23331668],["10^5",2333316668],["10^6",233333166668],
["10^7",23333331666668],["10^8",2333333316666668]]</
====With wheel increments====
<
var s=0, inc=[3,2,1,3,1,2,3]
for (var j=6, i=0; i<n; j+=j==6?-j:1, i+=inc[j]) s+=i
return s
}</
====With triangular numbers====
<
return tri(n,3) + tri(n,5) - tri(n,15)
function tri(n, f) {
Line 2,101:
return f * n * (n+1) / 2
}
}</
'''This:'''
<
document.write(10, '<sup>', i, '</sup> ', sm35(n), '<br>')
}</
{{out}}
10<sup>1</sup> 23
Line 2,119:
===ES6===
<
// sum35 :: Int -> Int
Line 2,259:
// ---
return main();
})();</
{{Out}}
<pre>Sums for n = 10^1 thru 10^8:
Line 2,272:
=={{header|jq}}==
<syntaxhighlight lang="jq">
def sum_multiples(d):
((./d) | floor) | (d * . * (.+1))/2 ;
Line 2,279:
def task(a;b):
. - 1
| sum_multiples(a) + sum_multiples(b) - sum_multiples(a*b);</
jq does not (yet) support arbitrary-precision integer arithmetic but converts large integers to floats, so:
<syntaxhighlight lang="jq">
1000 | task(3;5) # => 233168
10e20 | task(3;5) # => 2.333333333333333e+41</
=={{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)
Line 2,325:
(100000000000000000000,2333333333333333333316666666666666666668)</pre>
a slightly more efficient version
<
multsum(n, m, lim) = multsum(n, lim) + multsum(m, lim) - multsum(lcm(n,m), lim)</
=={{header|Kotlin}}==
<
import java.math.BigInteger
Line 2,359:
val e20 = big100k * big100k * big100k * big100k
println("The sum of multiples of 3 or 5 below 1e20 is ${sum35(e20)}")
}</
{{out}}
Line 2,368:
=={{header|Lasso}}==
<
while(#limit <= 100000) => {^
local(s = 0)
Line 2,376:
'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
Line 2,389:
Uses the IPints library when the result will be very large.
<
include "sys.m"; sys: Sys;
Line 2,461:
sub(isum_multiples(ints[15], limit)));
}
</syntaxhighlight>
{{out}}
Line 2,469:
=={{header|Lingo}}==
<
res = 0
repeat with i = 0 to (n-1)
Line 2,477:
end repeat
return res
end</
<
-- 233168</
=={{header|LiveCode}}==
<
repeat with i = 0 to (n-1)
if i mod 3 = 0 or i mod 5 = 0 then
Line 2,492:
end sumUntil
put sumUntil(1000) // 233168</
=={{header|Lua}}==
{{trans|Tcl}}
<syntaxhighlight lang="lua">
function tri (n) return n * (n + 1) / 2 end
Line 2,509:
print(sum35(1000))
print(sum35(1e+20))
</syntaxhighlight>
{{out}}
<pre>
Line 2,518:
=={{header|Maple}}==
By using symbolic function <code>sum</code> instead of numeric function <code>add</code> the program <code>F</code> will run O(1) rather than O(n).
<syntaxhighlight lang="maple">
F := unapply( sum(3*i,i=1..floor((n-1)/3))
+ sum(5*i,i=1..floor((n-1)/5))
Line 2,526:
F(10^20);
</syntaxhighlight>
Output:
<pre>
Line 2,546:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
Sum[k, {k, 3, n - 1, 3}] + Sum[k, {k, 5, n - 1, 5}] -
Sum[k, {k, 15, n - 1, 15}]
sum35[1000]</
{{out}}
<pre>233168</pre>
<syntaxhighlight lang
{{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);
(3*n3*(n3+1) + 5*n5*(n5+1) - 15*n15*(n15+1))/2</
<pre>ans = 233168</pre>
=={{header|Maxima}}==
<
[kmax],
Line 2,585:
sum35(1000);
sum35(10^20);</
Output:
<pre>
Line 2,597:
First, the simple implementation. It loops by threes and fives, and in the second loop, skips any multiples of five that are also divisible by three.
<
sum35 = function(n)
sum = 0
Line 2,609:
end function
print sum35(1000)</
{{out}}
<pre>233168</pre>
Line 2,615:
Now the fast version.
{{trans|D}}
<
sumMul = function(n, f)
n1 = floor((n - 1) / f)
Line 2,625:
end function
print sum35fast(1000)</
{{out}}
<pre>233168</pre>
=={{header|МК-61/52}}==
<syntaxhighlight lang="text">П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 С/П</
Input: ''n''.
Line 2,641:
{{trans|Java}}
This solution is translated from the simple Java version. Since all integers are arbitrary precision in Nanoquery, it is possible to use this solution for large n, but it is inefficient.
<
sum = 0
for i in range(3, n - 1)
Line 2,651:
end
println getSum(1000)</
{{out}}
<pre>233168</pre>
Line 2,657:
=={{header|NetRexx}}==
Portions translation of [[#Raku|Raku]]
<
options replace format comments java crossref symbols nobinary
numeric digits 40
Line 2,734:
say
return
</syntaxhighlight>
{{out}}
<pre>
Line 2,793:
=={{header|Nim}}==
Here is the solution using normal integers.
<
for x in 0 ..< n:
if x mod 3 == 0 or x mod 5 == 0:
result += x
echo sum35(1000)</
{{out}}
Line 2,807:
{{trans|Raku}}
{{libheader|bigints}}
<
proc sumMults(first: int32, limit: BigInt): BigInt =
Line 2,822:
while x < "1000000000000000000000000000000".initBigInt:
echo sum35 x
x *= 10</
{{out}}
Line 2,858:
=={{header|Objeck}}==
{{trans|Java}}
<
function : native : GetSum(n : Int) ~ Int {
sum := 0;
Line 2,874:
}
}
</syntaxhighlight>
Output:
Line 2,882:
=={{header|OCaml}}==
<
let sum = ref 0 in
for i = 3 to (n - 1) do
Line 2,891:
print_endline (string_of_int (sum_mults 1000));;
</syntaxhighlight>
{{out}}
<pre>233168</pre>
=== Functional programming version (more idiomatic) ===
<
open Printf;;
Line 2,908:
printf "The sum of the multiples of 3 or 5 below 1000 is %d\n" (sum3or5 1000);;
</syntaxhighlight>
{{Out}}
<pre>
Line 2,916:
=={{header|Oforth}}==
<
Output:
Line 2,924:
=={{header|Ol}}==
<
(print
(fold (lambda (s x)
Line 2,930:
0 (iota 1000)))
; ==> 233168
</syntaxhighlight>
=={{header|PARI/GP}}==
<
a(n)=ct(n,3)+ct(n,5)-ct(n,15);
a(1000)
a(1e20)</
{{output}}
<pre>
Line 2,947:
{{works with|Free Pascal|2.6.2}}
<
function Multiple(x, y: integer): Boolean;
Line 2,969:
{ Show sum of all multiples less than 1000. }
writeln(SumMultiples(1000))
end.</
===alternative===
using gauss summation formula, but subtract double counted.
adapted translation of [[#Tcl|Tcl]]
<
//sum of all positive multiples of 3 or 5 below n
Line 2,994:
sum := sum-cntSumdivisibleBelowN(n,3*5);
writeln(sum);
end.</
output
<pre>233168</pre>
=={{header|Perl}}==
<
use v5.20;
use experimental qw(signatures);
Line 3,009:
}
say "The sum is ${\(sum_3_5 1000)}!\n" ;</
{{Out}}
<pre>The sum is 233168!</pre>
Line 3,015:
{{Trans|Tcl}}
An alternative approach, using the analytical solution from the Tcl example.
<
use experimental qw(signatures);
Line 3,032:
say sum 1e3;
use bigint; # Machine precision was sufficient for the first calculation
say sum 1e20;</
{{Out}}
<pre>233168
Line 3,041:
===native===
note the result of sum35() is inaccurate above 2^53 on 32-bit, 2^64 on 64-bit.
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">sumMul</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
Line 3,058:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s%s%s %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">sp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sum35</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">))})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 3,075:
{{libheader|Phix/mpfr}}
Fast analytical version with arbitrary precision
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 3,104:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_free</span><span style="color: #0000FF;">({</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">})</span>
<!--</
{{Out}}
<pre>
Line 3,134:
Naive version (slow) :
<
$sum = 0;
for ($i = 1 ; $i < $max ; $i++) {
Line 3,142:
}
echo $sum, PHP_EOL;
</syntaxhighlight>
{{out}}
Line 3,149:
Fast version:
<
// Number of multiples of $divisor <= $max
$num = floor($max / $divisor);
Line 3,160:
+ sum_multiples($max - 1, 5)
- sum_multiples($max - 1, 15);
echo $sum, PHP_EOL;</
{{out}}
Line 3,170:
These functions allow for arbitrary-length integers to be worked with.
<
// Number of multiples of $divisor <= $max
$num = gmp_div($max, $divisor);
Line 3,188:
);
printf('%22s : %s' . PHP_EOL, gmp_strval($n), $sum);
}</
{{out}}
Line 3,216:
=={{header|Picat}}==
Uses both the naive method and inclusion/exclusion.
<syntaxhighlight lang="picat">
sumdiv(N, D) = S =>
M = N div D,
Line 3,227:
writef("The sum of all multiples of 3 and 5 below 1000 is %w%n", Upto1K),
writef("The sum of all multiples less than 1e20 is %w%n", sum35big(99999_99999_99999_99999)).
</syntaxhighlight>
{{Out}}
<pre>
Line 3,234:
</pre>
=={{header|PicoLisp}}==
<
(let N1 (/ (dec N) F)
(*/ F N1 (inc N1) 2) ) )
Line 3,243:
(-
(+ (sumMul N 3) (sumMul N 5))
(sumMul N 15) ) ) ) )</
{{out}}
<pre>
Line 3,269:
=={{header|PL/I}}==
<
declare (i, n) fixed(10), sum fixed (31) static initial (0);
Line 3,281:
put edit ( trim(sum) ) (A);
end threeor5;</
Outputs:
<pre>
Line 3,292:
=={{header|PowerShell}}==
<
function SumMultiples ( [int]$Base, [int]$Upto )
{
Line 3,302:
# Calculate the sum of the multiples of 3 and 5 up to 1000
( SumMultiples -Base 3 -Upto 1000 ) + ( SumMultiples -Base 5 -Upto 1000 ) - ( SumMultiples -Base 15 -Upto 1000 )
</syntaxhighlight>
{{out}}
<pre>
Line 3,308:
</pre>
For arbitrarily large integers, simply change the variable type.
<
function SumMultiples ( [bigint]$Base, [bigint]$Upto )
{
Line 3,319:
$Upto = [bigint]::Pow( 10, 210 )
( SumMultiples -Base 3 -Upto $Upto ) + ( SumMultiples -Base 5 -Upto $Upto ) - ( SumMultiples -Base 15 -Upto $Upto )
</syntaxhighlight>
{{out}}
<pre>
Line 3,325:
</pre>
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
Line 3,355:
}
$Sum
}</
{{out}}
<pre>Get-SumOfMultiples</pre>
Line 3,365:
=={{header|Prolog}}==
===Slow version===
<
sum_of_multiples_of_3_and_5(N, 1, 0, TT).
Line 3,381:
sum_of_multiples_of_3_and_5(N, K1, C5, S).
</syntaxhighlight>
===Fast version===
<
maplist(compute_sum(N), [3,5,15], [TT3, TT5, TT15]),
TT is TT3 + TT5 - TT15.
Line 3,393:
; N2 is N div N1),
Sum is N1 * N2 * (N2 + 1) / 2.
</syntaxhighlight>
Output :
Line 3,404:
=={{header|PureBasic}}==
<syntaxhighlight lang="purebasic">
EnableExplicit
Line 3,425:
CloseConsole()
EndIf
</syntaxhighlight>
{{out}}
Line 3,434:
=={{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
Line 3,465:
# Scalability
p = 20
print('\nFor n = %20i -> %i' % (10**p, sum35c(10**p)))</
{{out}}
Line 3,483:
Or, more generally – taking the area under the straight line between the first multiple and the last:
{{Works with|Python|3.7}}
<
Line 3,553:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Summed multiples of 3 and 5 up to n:
Line 3,572:
=={{header|Q}}==
<
s35 each 10 100 1000 10000 1000000</
Extra credit, using the summation formula:
<
s35:{a:x-1; (3*sn floor a%3) + (5*sn floor a%5) - (15*sn floor a%15)}
s35 e+10</
=={{header|Quackery}}==
<
[ 1 -
Line 3,592:
1000 sum-of-3s&5s echo cr
10 20 ** sum-of-3s&5s echo cr</
{{out}}
Line 3,602:
=={{header|R}}==
<
seq(3, n-1, by = 3), seq(5, n-1, by = 5))))
m35(1000) # 233168</
=={{header|Racket}}==
<
#lang racket
(require math)
Line 3,634:
(for/list ([k 20]) (analytical k))
</syntaxhighlight>
Output:
<
'(0 23 2318 233168 23331668 2333316668 233333166668)
'(0
Line 3,658:
233333333333333333166666666666666668
23333333333333333331666666666666666668)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
say sum35 1000;</
{{out}}
<pre>233168</pre>
Here's an analytical approach that scales much better for large values.
<syntaxhighlight lang="raku"
(my $last = $limit - 1) -= $last % $first;
($last div $first) * ($first + $last) div 2;
Line 3,677:
}
say sum35($_) for 1,10,100...10**30;</
{{out}}
<pre>0
Line 3,713:
=={{header|REXX}}==
===version 1===
<
* 14.05.2013 Walter Pachl
**********************************************************************/
Line 3,724:
s=s+i
End
Return s</
Output:
<pre>233168</pre>
===version 2===
<
* Translation from Raku->NetRexx->REXX
* 15.05.2013 Walter Pachl
Line 3,752:
last = last - last // first
sum = (last % first) * (first + last) % 2
return sum</
Output:
<pre> 1 0
Line 3,791:
The formula used is a form of the Gauss Summation formula.
<
parse arg N t . /*obtain optional arguments from the CL*/
if N=='' | N=="," then N= 1000 /*Not specified? Then use the default.*/
Line 3,806:
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
sumDiv: procedure; parse arg x,d; $= x % d; return d * $ * ($+1) % 2</
{{out|output|text= when using the default input:}}
<pre>
Line 3,908:
=={{header|Ring}}==
<
see sum35(1000) + nl
Line 3,919:
func tri n
return n * (n + 1) / 2
</syntaxhighlight>
=={{header|Ruby}}==
Simple Version (Slow):
<
(1...n).select{|i|i%3==0 or i%5==0}.sum
end
puts sum35(1000) #=> 233168</
Fast Version:
<
#
# Nigel_Galloway
Line 3,941:
# For extra credit
puts g(3,5,100000000000000000000-1)</
{{out}}
Line 3,951:
Other way:
{{trans|D}}
<
n1 = (n - 1) / f
f * n1 * (n1 + 1) / 2
Line 3,962:
for i in 1..20
puts "%2d:%22d %s" % [i, 10**i, sum35(10**i)]
end</
{{out}}
Line 3,989:
=={{header|Run BASIC}}==
<
end
function multSum35(n)
Line 3,995:
If (i mod 3 = 0) or (i mod 5 = 0) then multSum35 = multSum35 + i
next i
end function</
=={{header|Rust}}==
<
extern crate rug;
Line 4,035:
}
}
</syntaxhighlight>
Output :
<pre>
Line 4,050:
=={{header|Scala}}==
<
// Simplest solution but limited to Ints only
Line 4,070:
{
for( i <- (0 to 20); n = "1"+"0"*i ) println( (" " * (21 - i)) + n + " => " + (" " * (21 - i)) + sum35(BigInt(n)) )
}</
{{out}}
<pre> 1 => 0
Line 4,095:
=={{header|Scheme}}==
<
Output:
Line 4,104:
Or, more clearly by decomposition:
<
(or (zero? (remainder x 3))
(zero? (remainder x 5))))
Line 4,111:
(+ tot (if (fac35? x) x 0)))
(fold fac35filt 0 (iota 1000))</
Output:
Line 4,120:
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)))
Line 4,130:
(fast35sum 1000)
(fast35sum 100000000000000000000)
</syntaxhighlight>
Output:
Line 4,139:
=={{header|Seed7}}==
<
include "bigint.s7i";
Line 4,163:
writeln(sum35(1000_));
writeln(sum35(10_ ** 20));
end func;</
{{out}}
Line 4,173:
=={{header|Sidef}}==
{{trans|Ruby}}
<
var m = int((n - 1) / f)
f * m * (m + 1) / 2
Line 4,184:
for i in (1..20) {
printf("%2s:%22s %s\n", i, 10**i, sum35(10**i))
}</
{{out}}
<pre>
Line 4,211:
=={{header|Simula}}==
(referenced from [[Greatest common divisor#Simula|Greatest common divisor]])
<
! Project Euler problem 1: multiples of 3 or 5 below 1000 & 10**20;
BEGIN
Line 4,264:
OUTIMAGE
END
END</
{{out}}
sum of positive multiples of 3 and 5: 233168<br />
Line 4,277:
=={{header|Stata}}==
=== With a dataset ===
<
set obs 999
gen a=_n
tabstat a if mod(a,3)==0 | mod(a,5)==0, statistic(sum)</
=== With Mata ===
<
a=1..999
sum(a:*(mod(a,3):==0 :| mod(a,5):==0))</
=={{header|Swift}}==
<
Line 4,309:
print(sumofmult)
</syntaxhighlight>
=={{header|Tcl}}==
<
proc mul35sum {n} {
for {set total [set threes [set fives 0]]} {$threes<$n||$fives<$n} {} {
Line 4,328:
}
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
Line 4,338:
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...
puts [sum35 100000000000000000000]</
{{out}}
<pre>233168,233168
Line 4,356:
Only works up to 1000000000 due to limits of shell integer representation.
<
typeset -i n=$1 limit=$2
typeset -i max=limit-1
Line 4,372:
for (( l=1; l<=1000000000; l*=10 )); do
printf '%10d\t%18d\n' "$l" "$(sum35 "$l")"
done</
{{Out}}
Line 4,387:
=={{header|VBA}}==
{{trans|VBScript}}
<
Dim i As Double
For i = 1 To n - 1
Line 4,394:
End If
Next
End Function</
Other way :
<
Dim i As Double
For i = 3 To n - 1 Step 3
Line 4,404:
If i Mod 15 <> 0 Then SumMult3and5 = SumMult3and5 + i
Next
End Function</
Better way :
<
Dim i As Double
For i = 3 To n - 1 Step 3
Line 4,417:
SumMult3and5BETTER = SumMult3and5BETTER - i
Next
End Function</
Call :
<
Sub Main()
Line 4,432:
Debug.Print "-------------------------"
Debug.Print SumMult3and5BETTER(1000)
End Sub</
{{Out}}
<pre>2,33333331666667E+15 9,059 sec.
Line 4,443:
=={{header|VBScript}}==
{{trans|Run BASIC}}
<syntaxhighlight lang="vb">
Function multsum35(n)
For i = 1 To n - 1
Line 4,454:
WScript.StdOut.Write multsum35(CLng(WScript.Arguments(0)))
WScript.StdOut.WriteLine
</syntaxhighlight>
{{Out}}
Line 4,464:
=={{header|Verilog}}==
<
integer i, suma;
Line 4,477:
$finish ;
end
endmodule</
=={{header|Vlang}}==
{{trans|go}}
<
mut nn := n-1
mut threes := nn/3
Line 4,498:
fn main(){
println(s35(1000))
}</
{{out}}
<pre>
Line 4,505:
=={{header|Wortel}}==
<
sum35 ^(@sum \!-@(\~%%3 || \~%%5) @til)
!sum35 1000 ; returns 233168
}</
=={{header|Wren}}==
===Simple version===
<
n = n - 1
var s3 = (n/3).floor
Line 4,524:
}
System.print(sum35.call(1000))</
{{out}}
Line 4,535:
{{libheader|Wren-gmp}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
Line 4,558:
System.print(sum35)
limit.mul(10)
}</
{{out}}
Line 4,592:
=={{header|XPL0}}==
<
func Sum1; \Return sum the straightforward way
Line 4,633:
StrNSub(S, T, 40);
TextN(0, T, 40); CrLf(0);
]</
{{out}}
Line 4,644:
=={{header|Zig}}==
Inclusion/Exclusion mapping i64 -> i128 (largest integers supported in Zig natively)
<syntaxhighlight lang="zig">
const std = @import("std");
const stdout = std.io.getStdOut().writer();
Line 4,661:
try stdout.print("The sum of the multiples of 3 and 5 below 1e18 is {}\n", .{sum3or5(999_999_999_999_999_999)});
}
</syntaxhighlight>
{{Out}}
<pre>
Line 4,669:
=={{header|zkl}}==
Brute force:
<
233168</
{{trans|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).
<
fcn sum35(N){sumMul(N,3) + sumMul(N,5) - sumMul(N,15)}</
{{out}}
<pre>
|