## DEV Community π©βπ»π¨βπ» is a community of 963,864 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Peter Kim Frank

Posted on • Updated on

# Project Euler #1 - Multiples of 3 and 5

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!

Massimo Artizzu • Edited on

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.

tang

yesss the Gaussian sum is such a good tool!

Nested Software

This is very clever and very nice!

Pierre Bouillon

I did this in LOLCODE (first program that I'm writing with it, probably not the best implementation)

``````HAI 1.2
CAN HAS STDIO?
I HAS A GOAL ITZ 1000
I HAS A TOTAL ITZ 0

I HAS A VAR ITZ 0
IM IN YR LOOP UPPIN YR VAR TIL BOTH SAEM VAR AN GOAL
BOTH SAEM 0 AN MOD OF VAR AN 3
O RLY?
YA RLY
TOTAL R SUM OF TOTAL AN VAR
NO WAI
BOTH SAEM 0 AN MOD OF VAR AN 5
O RLY?
YA RLY
TOTAL R SUM OF TOTAL AN VAR
OIC
OIC
IM OUTTA YR LOOP

VISIBLE TOTAL

KTHXBYE
``````

Phil Nash

πππππ

Pierre Bouillon

You can try it here

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.

Joe Zack

short AND legible!

Sung M. Kim

Thanks Joe :)

Phil Nash • Edited on

## 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
``````

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

Matheus Calegaro • Edited on

Here it is Β―\_(γ)_/Β―
I'm looking forward for feedbacks

``````let sum = 0,
i = 0

for (i = 0; i < 1000; i++) {
if (i % 3 === 0 || i % 5 === 0) sum += i
}

console.log('The sum is %d', sum)
``````

Guillaume Martigny

Smallest nitpicking ever: declare `i` inside the `for` loop.

``````for (let i = 0; i < 1000; i++)
``````

It will prevent it from leaking outside the loop.

Jacob Evans

I wouldn't even call that nitpicking, that is solid best practice advice to avoid memory leaks.

Michael Kohl • Edited on

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
``````

Raunak Ramakrishnan

Here's one in Haskell using list comprehension:

``````sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]
``````

Florian Rohrer

Python

``````print(sum(i for i in range(1001) if i % 3 == 0 or i % 5 == 0))
``````

Florian Rohrer

For fun: A shorter solution.

``````sum({*range(3, 1000, 3)} | {*range(5, 1000, 5)})
``````

Aswath KNM

Great solution. Since I lost touch of python it was a little difficult. Now I understand.

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

Alain Van Hout

In Java

``````    final int sum = IntStream.range(0, 1000)
.filter(x -> x % 3 == 0 || x % 5 == 0)
.sum();
System.out.println(sum);
``````

Gabi • Edited on

Hi, I am adding my first thought on this in Java.

private int sum(int inputValue) {
int sum = 0;
for (int i = 1; i < inputValue; i++) {
if (i % 5 == 0 || i % 3 == 0) {
sum += i;
}
}
return sum;
}

Meghan (she/her) • Edited on
``````new Uint16Array(1000)
.map((v,i) => i)
.filter((v) => v % 3 == 0 || v % 5 === 0)
.reduce((ac,cv) => ac + cv)

// 233168
``````

Ronaldo Peres

Hi,
I am trying to solve this one, and already solved.

I am going to ask, what is the sum of all the multiples of 3 or 5 below 100000??

I am trying to do this but is giving me a timeout, when using loops.

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

``````

Frederik π¨βπ»β‘οΈπ Creemers
``````result = sum(x for x in range(1001) if x % 3 == 0 or x % 5 == 0)
``````