Sum multiples of 3 and 5: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 717: | Line 717: | ||
> (sum-3-5-fast 1000000000000000000000) |
> (sum-3-5-fast 1000000000000000000000) |
||
233333333333333333333166666666666666666668</pre> |
233333333333333333333166666666666666666668</pre> |
||
=={{header|Component Pascal}}== |
=={{header|Component Pascal}}== |
||
Line 859: | Line 857: | ||
233168 |
233168 |
||
2333333333333333333316666666666666666668</pre> |
2333333333333333333316666666666666666668</pre> |
||
=={{header|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> |
|||
{{out}} |
|||
<pre>233168</pre> |
|||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
Line 894: | Line 881: | ||
writeln(sum); |
writeln(sum); |
||
end.</lang> |
end.</lang> |
||
{{out}} |
|||
<pre>233168</pre> |
|||
=={{header|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> |
|||
{{out}} |
{{out}} |
||
<pre>233168</pre> |
<pre>233168</pre> |
||
Line 1,213: | Line 1,211: | ||
1000000000000000000 233333333333333333166666666666666668 ok |
1000000000000000000 233333333333333333166666666666666668 ok |
||
</lang> |
</lang> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
The method here recalls the story of the young Gauss being set the problem of adding up all the integers from one to a hundred by a master who wanted some peace and quiet from his class. The trick here is to apply the formula for multiples of three and for five, then remember that multiples of fifteen will have been counted twice. |
The method here recalls the story of the young Gauss being set the problem of adding up all the integers from one to a hundred by a master who wanted some peace and quiet from his class. The trick here is to apply the formula for multiples of three and for five, then remember that multiples of fifteen will have been counted twice. |
||
Line 1,322: | Line 1,321: | ||
The sum of all multiples less than 1e20 is 2333333333333333333316666666666666666668 |
The sum of all multiples less than 1e20 is 2333333333333333333316666666666666666668 |
||
</pre> |
</pre> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
<lang go>package main |
<lang go>package main |
||
Line 1,507: | Line 1,507: | ||
</lang> |
</lang> |
||
=={{header|Java}}== |
|||
===Simple Version=== |
|||
<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> |
|||
{{out}} |
|||
<pre>233168</pre> |
|||
===Extra Credit=== |
|||
<lang Java> |
|||
import java.math.BigInteger; |
|||
public class SumMultiples { |
|||
public static void main(String[] args) { |
|||
BigInteger m1 = BigInteger.valueOf(3); |
|||
BigInteger m2 = BigInteger.valueOf(5); |
|||
for ( int i = 1 ; i <= 25 ; i++ ) { |
|||
BigInteger limit = BigInteger.valueOf(10).pow(i); |
|||
System.out.printf("Limit = 10^%d, answer = %s%n", i, sumMultiples(limit.subtract(BigInteger.ONE), m1, m2)); |
|||
} |
|||
} |
|||
// Use Inclusion - Exclusion |
|||
private static BigInteger sumMultiples(BigInteger max, BigInteger n1, BigInteger n2) { |
|||
return sumMultiple(max, n1).add(sumMultiple(max, n2)).subtract(sumMultiple(max, n1.multiply(n2))); |
|||
} |
|||
private static BigInteger sumMultiple(BigInteger max, BigInteger m) { |
|||
BigInteger maxDivM = max.divide(m); |
|||
return m.multiply(maxDivM.multiply(maxDivM.add(BigInteger.ONE))).divide(BigInteger.valueOf(2)); |
|||
} |
|||
// Used for testing |
|||
@SuppressWarnings("unused") |
|||
private static long sumMultiples(long max, long n1, long n2) { |
|||
return sumMultiple(max, n1) + sumMultiple(max, n2) - sumMultiple(max, n1 * n2); |
|||
} |
|||
private static long sumMultiple(long max, long n) { |
|||
long sum = 0; |
|||
for ( int i = 1 ; i <= max ; i++ ) { |
|||
if ( i % n == 0 ) { |
|||
sum += i; |
|||
} |
|||
} |
|||
return sum; |
|||
} |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
Limit = 10^1, answer = 23 |
|||
Limit = 10^2, answer = 2318 |
|||
Limit = 10^3, answer = 233168 |
|||
Limit = 10^4, answer = 23331668 |
|||
Limit = 10^5, answer = 2333316668 |
|||
Limit = 10^6, answer = 233333166668 |
|||
Limit = 10^7, answer = 23333331666668 |
|||
Limit = 10^8, answer = 2333333316666668 |
|||
Limit = 10^9, answer = 233333333166666668 |
|||
Limit = 10^10, answer = 23333333331666666668 |
|||
Limit = 10^11, answer = 2333333333316666666668 |
|||
Limit = 10^12, answer = 233333333333166666666668 |
|||
Limit = 10^13, answer = 23333333333331666666666668 |
|||
Limit = 10^14, answer = 2333333333333316666666666668 |
|||
Limit = 10^15, answer = 233333333333333166666666666668 |
|||
Limit = 10^16, answer = 23333333333333331666666666666668 |
|||
Limit = 10^17, answer = 2333333333333333316666666666666668 |
|||
Limit = 10^18, answer = 233333333333333333166666666666666668 |
|||
Limit = 10^19, answer = 23333333333333333331666666666666666668 |
|||
Limit = 10^20, answer = 2333333333333333333316666666666666666668 |
|||
Limit = 10^21, answer = 233333333333333333333166666666666666666668 |
|||
Limit = 10^22, answer = 23333333333333333333331666666666666666666668 |
|||
Limit = 10^23, answer = 2333333333333333333333316666666666666666666668 |
|||
Limit = 10^24, answer = 233333333333333333333333166666666666666666666668 |
|||
Limit = 10^25, answer = 23333333333333333333333331666666666666666666666668 |
|||
</pre> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
Line 1,676: | Line 1,763: | ||
"100000":2333316668, "1000000":233333166668, "10000000":23333331666668, |
"100000":2333316668, "1000000":233333166668, "10000000":23333331666668, |
||
"100000000":2333333316666668}</lang> |
"100000000":2333333316666668}</lang> |
||
=={{header|Java}}== |
|||
===Simple Version=== |
|||
<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> |
|||
{{out}} |
|||
<pre>233168</pre> |
|||
===Extra Credit=== |
|||
<lang Java> |
|||
import java.math.BigInteger; |
|||
public class SumMultiples { |
|||
public static void main(String[] args) { |
|||
BigInteger m1 = BigInteger.valueOf(3); |
|||
BigInteger m2 = BigInteger.valueOf(5); |
|||
for ( int i = 1 ; i <= 25 ; i++ ) { |
|||
BigInteger limit = BigInteger.valueOf(10).pow(i); |
|||
System.out.printf("Limit = 10^%d, answer = %s%n", i, sumMultiples(limit.subtract(BigInteger.ONE), m1, m2)); |
|||
} |
|||
} |
|||
// Use Inclusion - Exclusion |
|||
private static BigInteger sumMultiples(BigInteger max, BigInteger n1, BigInteger n2) { |
|||
return sumMultiple(max, n1).add(sumMultiple(max, n2)).subtract(sumMultiple(max, n1.multiply(n2))); |
|||
} |
|||
private static BigInteger sumMultiple(BigInteger max, BigInteger m) { |
|||
BigInteger maxDivM = max.divide(m); |
|||
return m.multiply(maxDivM.multiply(maxDivM.add(BigInteger.ONE))).divide(BigInteger.valueOf(2)); |
|||
} |
|||
// Used for testing |
|||
@SuppressWarnings("unused") |
|||
private static long sumMultiples(long max, long n1, long n2) { |
|||
return sumMultiple(max, n1) + sumMultiple(max, n2) - sumMultiple(max, n1 * n2); |
|||
} |
|||
private static long sumMultiple(long max, long n) { |
|||
long sum = 0; |
|||
for ( int i = 1 ; i <= max ; i++ ) { |
|||
if ( i % n == 0 ) { |
|||
sum += i; |
|||
} |
|||
} |
|||
return sum; |
|||
} |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
Limit = 10^1, answer = 23 |
|||
Limit = 10^2, answer = 2318 |
|||
Limit = 10^3, answer = 233168 |
|||
Limit = 10^4, answer = 23331668 |
|||
Limit = 10^5, answer = 2333316668 |
|||
Limit = 10^6, answer = 233333166668 |
|||
Limit = 10^7, answer = 23333331666668 |
|||
Limit = 10^8, answer = 2333333316666668 |
|||
Limit = 10^9, answer = 233333333166666668 |
|||
Limit = 10^10, answer = 23333333331666666668 |
|||
Limit = 10^11, answer = 2333333333316666666668 |
|||
Limit = 10^12, answer = 233333333333166666666668 |
|||
Limit = 10^13, answer = 23333333333331666666666668 |
|||
Limit = 10^14, answer = 2333333333333316666666666668 |
|||
Limit = 10^15, answer = 233333333333333166666666666668 |
|||
Limit = 10^16, answer = 23333333333333331666666666666668 |
|||
Limit = 10^17, answer = 2333333333333333316666666666666668 |
|||
Limit = 10^18, answer = 233333333333333333166666666666666668 |
|||
Limit = 10^19, answer = 23333333333333333331666666666666666668 |
|||
Limit = 10^20, answer = 2333333333333333333316666666666666666668 |
|||
Limit = 10^21, answer = 233333333333333333333166666666666666666668 |
|||
Limit = 10^22, answer = 23333333333333333333331666666666666666666668 |
|||
Limit = 10^23, answer = 2333333333333333333333316666666666666666666668 |
|||
Limit = 10^24, answer = 233333333333333333333333166666666666666666666668 |
|||
Limit = 10^25, answer = 23333333333333333333333331666666666666666666666668 |
|||
</pre> |
|||
=={{header|jq}}== |
=={{header|jq}}== |
||
Line 2,507: | Line 2,506: | ||
2333333333333333333316666666666666666668</pre> |
2333333333333333333316666666666666666668</pre> |
||
Interestingly, the prime factorization of the second result produces a 35 digit prime number. |
Interestingly, the prime factorization of the second result produces a 35 digit prime number. |
||
=={{header|Perl 6}}== |
|||
<lang perl6>sub sum35($n) { [+] grep * %% (3|5), ^$n; } |
|||
say sum35 1000;</lang> |
|||
{{out}} |
|||
<pre>233168</pre> |
|||
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> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 3,136: | Line 3,085: | ||
23333333333333333331666666666666666668) |
23333333333333333331666666666666666668) |
||
</lang> |
</lang> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
<lang perl6>sub sum35($n) { [+] grep * %% (3|5), ^$n; } |
|||
say sum35 1000;</lang> |
|||
{{out}} |
|||
<pre>233168</pre> |
|||
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> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Line 3,419: | Line 3,419: | ||
next i |
next i |
||
end function</lang><pre>233168</pre> |
end function</lang><pre>233168</pre> |
||
=={{header|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> |
|||
{{out}} |
|||
<pre> 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</pre> |
|||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
Line 3,517: | Line 3,472: | ||
</pre> |
</pre> |
||
=={{header|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> |
|||
{{out}} |
|||
<pre> 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</pre> |
|||
=={{header|Scheme}}== |
=={{header|Scheme}}== |