Peter Kim Frank

Posted on Jun 11, 2018 • Edited on May 28, 2019

Project Euler #1 - Multiples of 3 and 5

#projecteuler #challenge

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!

Top comments (40)

Massimo Artizzu • Jun 11 '18 • Edited

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.

Nested Software • Jun 12 '18

This is very clever and very nice!

mari tang • May 29 '19

yesss the Gaussian sum is such a good tool!

Pierre Bouillon • Jun 12 '18

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 • Jun 12 '18

👏👏👏👏👏

Pierre Bouillon • Jun 12 '18

You can try it here

Sung M. Kim • Jun 12 '18

Answer in C# using LINQ.

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

Explanation

Enumerable.Range generates a number between 1 & 1000
Where filters records that matches a condition (It's like filter in JS)
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 • Jun 12 '18

short AND legible!

Sung M. Kim • Jun 12 '18

Thanks Joe :)

Phil Nash • Jun 12 '18 • Edited

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 • Jun 13 '18 • Edited

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 • Jun 12 '18 • Edited

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 • Jun 13 '18

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 • Sep 7 '19

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

Florian Rohrer • Jun 11 '18

Python

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

Florian Rohrer • Jun 11 '18

For fun: A shorter solution.

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

Aswath KNM • Jun 12 '18

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

Ali Spittel • May 28 '19

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

Seiei Miyagi • Jun 21 '18

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

Alain Van Hout • Jun 12 '18

In Java

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

Omkar Ajnadkar • Jun 13 '18 • Edited

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

View full discussion (40 comments)

Some comments may only be visible to logged-in visitors. Sign in to view all comments.

DEV Community

Project Euler #1 - Multiples of 3 and 5

Top comments (40)

Ruby

JavaScript

Python

Read next

AZ-104: Deploy and Manage Azure Compute Resources – Comprehensive Guide

Understanding Microsoft Entra ID (Formerly Azure Active Directory) for the Azure Administration Certification Exam-Az 104

LeetCode in Golang: Parsing A Boolean Expression

Judging the first DEV Web Game Challenge