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.