And at last but not at least, the haskell solution.

module FirstKata (
fkSum
) where
fkSum = foldl (+) 0 (filter (\x -> (mod x 3 == 0)
|| (mod x 5 == 0)) [1,2..999])

testFkSum = TestCase $ assertEqual 233168 fkSum

This first solution is the same as the java one, only it sintax is very different. Short story is, we have a function to compute all multiples of 3 or 5 less than 1000.

The function does exactly and only this.

fkSum :: Int -> Int
fkSum a = foldl (+) 0 (filter (\x -> (mod x 3 == 0)
|| (mod x 5 == 0)) [1..a])

testFkSum = TestCase $ assertEqual 233168 (fkSum 999)

A little refactor latter and we have a little more generic function.

It now takes a number (upperLimit) function parameter.

fkSum :: Int -> [Int] -> Int
fkSum a [] = 0
fkSum a (b) = foldl (+) 0 (filter (\x -> isMultiple x b) [1..a])
isMultiple :: Int -> [Int] -> Bool
isMultiple a [] = False
iisMultiple a (x:xs) =
if (mod a x == 0) then True else isMultiple a xs

testFkSumFirst = TestCase $ assertEqual 23 (fkSum 9 [3,5])
testFkSumSecond = TestCase $ assertEqual 233168 (fkSum 999 [3,5])
suite = TestList [ testFkSumFirst, testFkSumSecond ]

And now we have the most generic function in haskell as well.

After some tips, we can improve our solution.

The good thing about this new solution is that it executes in constant time no matter how big is the upper limit.

But, it comes with a price and it's that we don't have the most generic solution that can handle the universe. What we have now is a solution that

can find the sum of any pair of multiples for any given upper limit.

**The theory behing the solution.**
We had to apply the inclusion exclusion principle. This principle states that the number of elements in the union of two set is the elements of the first set plus the elements of the second set minus the elements that are in both.

So, given the above, we have

- sumOfMultiples of 3 or 5 less than 1000 = f 1000 3 + f 1000 5 - f 1000 15

Now we know what is the sum of the multiples of 3 or 5 less than 1000 but, wait... What is the sum of the multiples of 3 less than 1000? and the sum of multiples of 5 less than 1000?

To find out the sum of the individual multiples we have to use the first principle of finite induction that states that n * ( n + 1 ) / 2 to any given number n.

In this case, n is the number of multiples that we have to sum up. We find it by dividing the upper limit by the multiple

And by the latter we have:

- f 1000 3 = ( n * ( n + 1 ) / 2 ) * 3
- f 1000 5 = ( n * ( n + 1 ) / 2 ) * 5

By applying this function, we'll find out the value of the sum of any individual multiples.

**So, add all together and see what's look like.**
**Java**
public long sum(long upperLimit,
int firstMultiple,
int secondMultiple) {
return sumMultiples(upperLimit, firstMultiple)
+ sumMultiples(upperLimit, secondMultiple)
- sumMultiples(upperLimit,
firstMultiple * secondMultiple);
}
public long sumMultiples(long upperLimit, int multiple) {
long n = upperLimit / multiple;
return (n * (n + 1) / 2) * multiple;
}

**Ruby**
def sum(upper_limit, first_multiple, second_multiple)
first_sum = sum_multiples(upper_limit, first_multiple)
second_sum = sum_multiples(upper_limit, second_multiple)
third_sum = sum_multiples(upper_limit,
first_multiple * second_multiple)
first_sum + second_sum - third_sum
end
def sum_multiples(upper_limit, multiple)
n = upper_limit / multiple
j = (n * (n + 1) / 2) * multiple
end

**Scala**
def sum(upperLimit: Long, fm: Int, sm: Int): Long = {
return (sumMultiples(upperLimit, fm)
+ sumMultiples(upperLimit, sm)
- sumMultiples(upperLimit, fm * sm }
def sumMultiples(upperLimit: Long, multiple: Int): Long = {
val n: Long = upperLimit / multiple
return (n * (n + 1) / 2) * multiple
}

**Haskell**
module FirstKata (
fkSum
) where
fkSum u x y = f x + f y - f (x * y)
where f d = let n = u `div` d in (n * (n + 1) `div` 2) * d

I hope you have enjoyed the reading.