# Project Euler #1 - Multiples of 3 and 5 Peter Kim Frank Updated on ・1 min read

I thought it would be fun to create a thread where the community could solve a problem from Project Euler. This is Problem #1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Look forward to seeing solutions in your language of choice!

### Discussion  Massimo Artizzu

I'll take a mathematical approach.

The sum of the first n positive integers is n*(n + 1)/2. Multiply by k, and you get the sum of the first n multiples of k.

There are 333 multiples of 3 below 1000, and 199 multiples of 5, so we get 166833 and 99500, respectively. But we can't just sum them, as we'd count the multiples of 15 twice (15 is their least common multiple), so we have to subtract those once (total: 33165).

Result: 233168

In general, let's use JavaScript for example:

``````const limit = 1000;
const m = 3, n = 5;

const mulM = Math.floor((limit - 1) / m);
const mulN = Math.floor((limit - 1) / n);

const lcm = leastCommonMultiple(m, n);
const mulLcm = Math.floor((limit - 1) / lcm);

const result = m * mulM * (mulM + 1) / 2
+ n * mulN * (mulN + 1) / 2
- lcm * mulLcm * (mulLcm + 1) / 2;
``````

There, no iterations, pure math 👍 And blazing fast

Using JavaScript's new support of `BigInt`, it's immediate even with huge numbers like 123456789012345678901234567890: it's 3556368375755728575115582031196717989244271707186887161545. Sung M. Kim

``````Enumerable
.Range(1, 1000)
.Where(i => i % 3 == 0 || i % 5 == 0)
.Sum();
``````

Explanation

1. `Enumerable.Range` generates a number between 1 & 1000
2. `Where` filters records that matches a condition (It's like `filter` in JS)
3. `Sum` is a convenience method for summing up a sequence (instead of doing `Aggregate((acc, n) => acc + n))`, which is equivalent to `reduce` in JS)

Source & Tests on Github. Phil Nash

## Ruby

``````(1...1000).select { |n| n % 3 == 0 || n % 5 == 0 }.sum
# => 233168
``````

## JavaScript

It's a shame getting a range and a sum isn't quite as easy in JS.

``````Array.from(Array(1000).keys())
.filter(n => n % 3 === 0 || n % 5 === 0)
.reduce((acc, n) => acc + n);
// => 233168
`````` NC

Or generate the range with the es6 spread operator:

``````[...Array(1000).keys()]
.filter(n => n % 3 === 0 || n % 5 === 0)
.reduce((acc, n) => acc + n)
``````

There's also a nasty (but shorter) `eval` hack to use in place of reduce. You can use `.join(+)` to convert the array into a string containing each number joined by the '+' sign, then evaluate that string as if it's a JavaScript expression to get the sum:

``````eval([...Array(1000).keys()].filter(n => n % 3 === 0 || n % 5 === 0).join('+'))
``````

It's a bad practice to use eval, of course, but useful for JS code golf.

Or with lodash:

``````_(_.range(1, 1000)).filter(n => n % 3 === 0 || n % 5 === 0).sum()
`````` Michael Kohl

At last count I did that exercise in 11 different languages, so maybe I'll post some of the less common ones.

Clojure:

``````(defn problem1
[n]
(reduce + (filter #(or (= 0 (mod % 3)) (= 0 (mod % 5))) (range 1 n))))

(println (problem1 1000))
``````

``````main :: IO ()
main = print problem1

problem1 :: Integer
problem1 = sum (filter (\x -> x `mod` 3 == 0 || x `mod` 5 == 0) [1..999])
``````

Haskell (a bit more interesting, but wasteful):

``````import Data.List
problem1 = sum \$ nub \$ [3,6..999] ++ [5,10..999]
``````
``````Number dividesBy = (x):
self % x == 0.

sum = 0
1 to 999 (x):
if (x dividesBy(3) || x dividesBy(5)): sum += x
_x
(sum, "\n") join print
``````

GNU Smalltalk:

``````res := ((3 to: 999) select: [:i| (i \\ 3 = 0) | (i \\ 5 = 0)])
inject: 0 into: [:sum :i| sum+i].
res printNl
`````` Seiei Miyagi

Ruby✨💎✨

``````require "set"

multiples_of_3 = Enumerator.new {|y| x = 0; y << x while x += 3 }
multiples_of_5 = Enumerator.new {|y| x = 0; y << x while x += 5 }

puts [multiples_of_3, multiples_of_5].each_with_object(Set.new) { |e, s|
s.merge(e.take_while(&1000.method(:>)))
}.sum
`````` Ali Spittel
``````def sum_natural_numbers_below_n(n):
# O(N) complexity
mult_3 = range(3, n, 3)
mult_5 = range(5, n, 5)
all_multiples = set(mult_3 + mult_5)
return sum(all_multiples)

print(sum_natural_numbers_below_n(1000))
`````` Wing-Kam

C++

``````#include <bits/stdc++.h>
using namespace std;

long long t,i,x;

long long s(long long n,long long k){
// s3=3+6+9+..+3i    - 3i<=n
// s3=3(1+2+3+..+i)  - i <=n/3
// -------------------
//  z(i)=1+2+3+..+(i-1)+i
//  z(i)=i+(i-1)+(i-2)+...+2+1
// 2z(i)=(i+1)+(i+1)+(i+1)..+(i+1)+(i+1)
//  z(i)=i*(i+1)/2
// -------------------
// s3=3*(z(n/3))
// s3=3*((n/3)((n/3)+1)/2)
// sk=k*((n/k)((n/k)+1)/2)
x = n/k;
return (k*(x*(x+1)))/2;
}

long long  euler1(long long n){
return s(n,3) + s(n,5) - s(n,15);
}

int main()
{
cin >> t;
while(t--){
cin >> i;
cout << euler1(i-1) << "\n";
}
return 0;
}
`````` Stephen Leyva (He/Him)

Python implementation that runs in Θ(1) time

``````def solve(n):
three = 3 * sum_all(math.floor(n/3))
fives = 5 * sum_all(math.floor(n/5))
sames = 15 * sum_all(math.floor(n/15))
return three + fives - sames

def sum_all(n):
return n*(n+1)/2

`````` ### Python

``````sum = 0
for i in range(0,1000):
if i % 3 == 0 or i % 5 == 0:
sum = sum + i
print(sum)
``````

or Python One-Liner

``````print(sum(i for i in range(1000) if i % 3 == 0 or i % 5 == 0))
`````` rahy-hub

/*Multiples of 3 and 5

Problem 1
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000. */

# include

using namespace std;

int main()
{
int sum=0;
for(int i=1;i<1000;i++)
{
if(i%3==0 ||i%5==0)
{cout<<i<<" ";
sum+=i;}

}
cout<<"\n\n"<<"the sum of all the multiples of 3 or 5 below 1000 = "<<sum<<"\n";

return 0;
}

C++ >> Output >> 233168 Big-Zude

function multiple(){
var a=Math.trunc(999/3)
var b=Math.trunc(999/5)
var c=Math.trunc(999/15)

var multi3=((3*a)(a+1))/2
var multi5=((5*b)
(b+1))/2
var multi15=((15*c)*(c+1))/2

var sum=(multi3+multi5)-multi15
return sum
}
console.log(multiple()) Daniel Bruynooghe

k) +/&0=min{x-y*x div y}/:[;3 5](!)1000

For a change my k solution is more wordy because the mod function is rather long. Said that, the q above has k in it as well. In pure q it would read

q)sum where 0=min mod/:[;3 5]til 1000

terse and somewhat obfuscated, though the main elements are recognizable, i.e. create the list up to 1000, compute the remainders when dividing by 3 and by 5 and sum across all where either remainder is 0.  