loading...

Project Euler #1 - Multiples of 3 and 5

peter profile image 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

pic
Editor guide
Collapse
maxart2501 profile image
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.

Collapse
nestedsoftware profile image
Nested Software

This is very clever and very nice!

Collapse
tttaaannnggg profile image
tang

yesss the Gaussian sum is such a good tool!

Collapse
pbouillon profile image
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
Collapse
philnash profile image
Phil Nash

👏👏👏👏👏

Collapse
pbouillon profile image
Pierre Bouillon

You can try it here

Collapse
dance2die profile image
Sung M. Kim

Answer in C# using LINQ.

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.

Collapse
thejoezack profile image
Joe Zack

short AND legible!

Collapse
dance2die profile image
Sung M. Kim

Thanks Joe :)

Collapse
philnash profile image
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
Collapse
ndc profile image
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()
Collapse
citizen428 profile image
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))

Haskell (boring):

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]

Potion:

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
Collapse
rrampage profile image
Raunak Ramakrishnan

Here's one in Haskell using list comprehension:

sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]
Collapse
matheus profile image
Matheus Calegaro

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)
Collapse
gmartigny profile image
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.

Collapse
jacobmgevans profile image
Jacob Evans

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

Collapse
r0f1 profile image
Florian Rohrer

Python

print(sum(i for i in range(1001) if i % 3 == 0 or i % 5 == 0))
Collapse
r0f1 profile image
Florian Rohrer

For fun: A shorter solution.

sum({*range(3, 1000, 3)} | {*range(5, 1000, 5)})
Collapse
aswathm78 profile image
Aswath KNM

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

Collapse
hanachin profile image
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
Collapse
aspittel profile image
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))
Collapse
wingkwong profile image
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; 
}
Collapse
srleyva profile image
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

Collapse
_bigblind profile image
Frederik 👨‍💻➡️🌐 Creemers
result = sum(x for x in range(1001) if x % 3 == 0 or x % 5 == 0)
Collapse
alainvanhout profile image
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);
Collapse
blackbird profile image
Omkar Ajnadkar

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))
Collapse
ronaldoperes profile image
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.

Collapse
nektro profile image
Meghan (she/her)
new Uint16Array(1000)
.map((v,i) => i)
.filter((v) => v % 3 == 0 || v % 5 === 0)
.reduce((ac,cv) => ac + cv)

// 233168
Collapse
gabriela profile image
Gabi

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;
}

Collapse
derfugu profile image
Daniel Bruynooghe

q){sum x where 0=min x mod/:(3,5)}til 1000
k) {+/ &: 0=min x {x-y*x div y}/:(3,5)}(!)1000

or mix and match without lambdas is even shorter and more obfuscated
q)sum (&:) 0=min ((!)1000) mod/: (3,5)

Collapse
likelocusts profile image
LikeLocusts

Scala:

def sumOfMultiples(max: Int): Int = {
    if (max <= 0) 0
    else if (max % 3 == 0 || max % 5 == 0) max + sumOfMultiples(max - 1)
    else sumOfMultiples(max - 1)
  }  
Collapse
rahyhub profile image
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

Collapse
bigzude profile image
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())

Collapse
mraza007 profile image
Muhammad

I did that a while ago in C++

Collapse
jvarness profile image
Collapse
derfugu profile image
Daniel Bruynooghe

q)sum (&) 0=min mod/:[; 3 5](!)1000

Collapse
derfugu profile image
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.

Collapse
saigowthamr profile image
Sai gowtham
let sum=0;
let start=999;

 while(start){
    if(start % 3 === 0 || start % 5===0){
       sum +=start;
    }  
   start--;  
 }

console.log(sum);
Collapse
erhankilic profile image
Erhan Kılıç

I started to solve problems but, well, you know little time so I couldn't continue :) I created a repository at github.

github.com/erhankilic/project-eule...

Collapse
sawankrr profile image
sawankrr

Java

 Long sum = LongStream.range(1, 100)
                    .filter(i -> i % 3 == 0 || i % 5 == 0)
                    .sum();
    System.out.println(sum);
Collapse
ulvienzo profile image
ulvienzo

Hey, Why this doesn't work for 1000?

function multiplesOf3and5(number) {
var sum=0;
while(number>0){
if(number%3===0 || number%5===0){
sum+=number
}
number--
}
return sum;
}