reaktor42 - a personal platform

Project Euler: Problem 1

Let’s try to solve some Project Euler problems using Haskell. Its a good way to stress my math knowledge and Haskell knowledge, but its also a good way to frequently publish some stuff without writing about complete nonsense.

TL;DR … lets start with the first problem.

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.

Solution

To be honest this is a fairly easy question to solve using Haskell without being in the need to grasp the mathematical background though.

We just use sum in conjunction with a trivial list comprehension.

euler001 :: Int
euler001 = sum [n | n <- [3..999], n `mod` 3 == 0 || n `mod` 5 == 0]

Since modulo operations are considered expensive we may use us some Haskell range notation with a bit of thinking to simplify the computation. It’s importantent to subtract the sum of the duplicate multiples once.

euler001' :: Int
euler001' = sum [3,6..999] + sum [5,10..999] - sum [15,30..999]

Well, to see if we can do better in the sense of using less cpu cycles but a bit more brain power lets start to analyse what we just did. First of all we rewrite it as a mathematical equation.

\(\sum_{i=1}^{\lfloor\frac{999}{3}\rfloor}3i + \sum_{i=1}^{\lfloor \frac{999}{5}\rfloor}5i - \sum_{i=1}^{\lfloor\frac{999}{15}\rfloor}15i\)

Turns out equation is composed of three somewhat equally looking summations of a series, lets try to simplify the term.

\(\sum_{i=1}^{\lfloor\frac{999}{3}\rfloor}3 \cdot i = 3 \sum_{i=1}^{\lfloor\frac{999}{3}\rfloor}i = 3 \cdot \frac{\lfloor\frac{999}{3}\rfloor(\lfloor\frac{999}{3}\rfloor + 1)} {2}\)

Or generally speaking..

\(C\cdot\sum_{i=1}^{n}i = C \cdot \frac{n(n+1)}{2}\)

The final step is to transform this knowledge into a proper Haskell implementation.

euler001'' :: Int
euler001'' = sum' 3 + sum' 5 - sum' 15
  where
    sum' i = let n = 999 `div` i in i * n * (n + 1) `div` 2

The final implementation has a runtime behavior of \(O(1)\) instead of \(O(n)\) like our first naive implementation.