# Project Euler in Haskell #1

2012-04-08 — Article of 300 words - Available in Italiano Programming Haskell Project Euler

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