Project Euler in Haskell #1

Problem Description

Link to Project Euler 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.

WARNING Solution ahead. Don’t read more if you want to enjoy the benefits of Project Euler and you haven’t already solved the problem.

Solution

The simple way is to go through all numbers from 1 to 999 and test whether they are divisible by 3 or by 5. In Haskell you could use list comprehension:

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

Reading the solution notes from the project’s site, we can see that the solution could even be expressed as:

solution'  =  sum [n | n <- [1..999], n `mod` 3 == 0]  +
              sum [n | n <- [1..999], n `mod` 5 == 0]  -
              sum [n | n <- [1..999], n `mod` 15 == 0]

Noting that:

$$ 3+6+9+12+15+\dots+999 = 3\times(1+2+3+4+\dots+333) $$ $$ 5+10+15+\dots+995 = 5\times(1+2+\dots+199) $$

where $333=\frac{999}{3}$ and $199=\frac{995}{5}$ but also $\frac{999}{5}$ rounded down to the nearest integer.

And that from the expression for arithmetic progression:

$$ S_n=\frac{n}{2}(a_1+a_n) $$

we can derive that:

$$ 1+2+3+\dots{}+p=\frac{p}{2}(1+p) $$

We could write an efficient solution:

target = 999

sumDivisibleBy n = n * p * (1 + p) `div` 2
    where
      p = target `div` n

solution'' = sumDivisibleBy 3 + sumDivisibleBy 5 - sumDivisibleBy 15

You can find the Literate Haskell code on GitHub and on Bitbucket.