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!

Did you find this post useful? Show some love!

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.

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

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()
Ben Halpern DEV.TO FOUNDER

Hey there, we see you aren't signed in. (Yes you, the reader. This is a fake comment.)

Please consider creating an account on dev.to. It literally takes a few seconds and we'd appreciate the support so much. ❤️

Plus, no fake comments when you're signed in. 🙃

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.

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

Here's one in Haskell using list comprehension:

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

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)

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.

I like coding to follow the original problem definition. And then define these top-level functions in terms of smaller ones. E.g., Haskell:

[1..999] 
  & filter is_multiple_of_3_or_5 
  & sum


is_multiple_of_3_or_5 x = is_multiple_of 3 x || is_multiple_of 5 x

is_multiple_of a x      = gcd x a == a

Ruby:

class Integer
  def multiple_of?(x)
    self.remainder(x) == 0
  end
end


puts (1...1000)
       .to_a
       .keep_if { |i| i.multiple_of?(3) or i.multiple_of?(5) }
       .sum

Python

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

For fun: A shorter solution.

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

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

new Uint16Array(1000)
.map((v,i) => i)
.filter((v) => v % 3 == 0 || v % 5 === 0)
.reduce((ac,cv) => ac + cv)

// 233168

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

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

In Java

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

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

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)
  }  
let sum=0;
let start=999;

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

console.log(sum);

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

Classic DEV Post from Dec 22 '17

How we can make a difference as software engineers

As the holiday season rolls around again the idea of doing good in the world ...

READ POST
Follow @amandasopkin to see more of their posts in your feed.
Peter Kim Frank
Working on dev.to. Previously: on-demand tutoring and textbooks. Before that, ran/sold an online community and worked for the company that built Tinder. 😎
More from @peter
Project Euler #3 - Largest Prime Factor
#projecteuler #challenge
Project Euler #2 - Even Fibonacci numbers
#projecteuler #challenge
Trending on dev.to
Does anyone else feel bothered when people term us as coders instead of developers or programmers..?
#discuss
5 Reasons You Should Write That Blog Post
#career #beginners
Its 2018, why are you still going to the office?
#discuss
What's a recent frustrating bug you've had with a crazy simple solution?
#debugging #discuss #php
Biggest aha moment
#discuss
A better way to handle magic values and constants?
#discuss
How to deal with being laid off?
#work #job #development #discuss
Ever feel like you have "Programming Synesthesia"?
#discuss #programming #productivity