brokensandals.net -> Project Euler #1

Published on 2019-05-20.

These early Project Euler problems are fairly basic in terms of both the programming and math skills required, but you can still learn interesting things from working on them. I used the opportunity to teach myself a little about Kotlin, and to learn a little math in the pursuit of optimized solutions.

# Problem 1: Multiples of 3 and 5

The problem statement from https://projecteuler.net/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 1: Brute force

The most obvious approach is:

1. Look at every number between 3 and 999. (We stop at 999, not 1000, since the problem says “below 1000”.)
2. Check whether it’s divisible by 3 or by 5.
3. If so, add it to the sum.

Here’s the code in Kotlin, which will give the correct answer:

```fun main() {
var sum = 0

for (i in 3 until 1000) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i
}
}

println(sum)
}```
Kotlin language notes
• `3 until 1000` specifies a range from 3 to 999. If you wanted a range from 3 to 1000 you'd use `3..1000`.
• As in many programming langues, `i % 3` gives you the remainder of dividing `i` by 3. So when it's zero, you know the number is evenly divisible by 3.

An approach like this is called “brute forcing” because it doesn’t use any sophisticated tactics to try to get the answer quickly or efficiently. It relies on the computer’s computational power to work through an exhaustive list of calculations, just as you might use your physical power to bash through a locked door rather than search for a key.

In this case, that means performing one or two divisions on every number between 3 and 999. That’s not much work at all for a computer; it will finish practically instantly.

So for such a small number, for this problem, the brute force approach works great. In fact, it works for even much larger numbers:

```fun main() {
var sum = 0L

for (i in 3 until Int.MAX_VALUE) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i
}
}

println(sum)
}```

`Int.MAX_VALUE` is `(2^31)-1`, which is 2,147,483,647. The above program will complete in just a few seconds and print a number greater than one quintillion.

## Solution 2: Functional-style brute force

Before considering more efficient solutions, let’s look at another way of writing solution 1:

```fun main() {
println((3 until 1000)
.filter { it % 3 == 0 || it % 5 == 0 }
.sum())
}```

This is essentially the same algorithm - it still requires the computer to look at every number between 3 and 999, and to perform one or two divisions on each of those numbers. But it’s written in the style of functional programming.

Let’s break down roughly what the code above says:

1. `(3 until 1000)`: Give me a list of all numbers from 3 to 999.
2. `.filter { ... }`: Give me a new list based on that list, but only containing the numbers that are divisble by 3 or 5.
3. `.sum()`: Add up all the numbers in that list and give me the result.

Notice that there are no changing variables anywhere. Avoiding mutable state (such as variables that get assigned multiple values over the course of the program) is one of the hallmarks of functional programming.

## Solution 3: Loop over multiples

It’s easy to loop over all the multiples of 3. Just set a variable to 3, and then increment the variable by 3 on each iteration of the loop. You could do the same for 5, obviously. So instead of looping over all the numbers from 3 to 999 like the brute force solution does, we should be able to only loop over the multiples of 3 and 5. But you do have to make sure not to double-count numbers that are multiples of both, such as 15.

First we’ll look at a somewhat confusing way to do this, and then in solution 4 we’ll look at a more elegant approach.

```fun main() {
val end = 1000
var mul3 = 3
var mul5 = 5
var sum = mul3 + mul5

while (mul3 < end || mul5 < end) {
if (mul3 < mul5) {
mul3 += 3
if (mul3 < end && mul3 != mul5) {
sum += mul3
}
} else {
mul5 += 5
if (mul5 < end && mul3 != mul5) {
sum += mul5
}
}
}

println(sum)
}```
Kotlin language notes
• `val` indicates a variable whose value does not change. `mul3`, `mul5`, and `sum` are `var`s because we add to them within the loop. `end` is a `val` because it's simply holding the end of the range, which doesn't change.

This algorithm uses a single loop to iterate over all the multiiples of 3 and all the multiples of 5.

Three variables are used:

• `mul3`: the most recent multiple of 3 we’ve found
• `mul5`: the most recent multiple of 5 we’ve found
• `sum`: the total sum of all multiples of 3 or 5 we’ve found so far

Each iteration will either find the next multiple of 3 and update `mul3`, or find the next multiple of 5 and update `mul5`.

In either case, it adds the new multiple to `sum`, unless that multiple was already found in the previous iteration. If the multiple was found in the previous iteration, then it must be a multiple of both 3 and 5.

For this to work correctly, it’s important that we always choose to update `mul3` or `mul5` based on which one is currently lower. This ensures that when a number is a multiple of both 3 and 5, as soon as one iteration of the loop discovers it as a multiple of one number, the very next iteration will discover it as a multiple of the other number. In that second iteration, `mul3` and `mul5` will be equal. So we can avoid double-counting numbers that are multiples of both 3 and 5 by not updating `sum` when `mul3 == mul5`.

The following table shows what each variable’s value is at the end of the loop, for the first ten iterations of the loop. The numbers in bold are what the program added to `sum` during that iteration of the loop.

Iteration `mul3` `mul5` `sum`
start 3 5 8
1 6 5 14
2 6 10 24
3 9 10 33
4 12 10 45
5 12 15 60
6 15 15 60
7 15 20 80
8 18 20 98
9 21 20 119
10 21 25 144

Notice iterations 5 and 6, where we encounter the first multiple of both 3 and 5. It’s first discovered as a multiple of 5 and added to `sum`. The next iteration discovers it as a multiple of 3, and does nothing, since the previous iteration already discovered it.

## Solution 4: Looping sum of multiples function

Solution 3 is difficult to follow because it tries to have a single loop handle finding the multiples of 3 as well as the multiples of 5 simultaneously. This requires some complexity to ensure that numbers which are multiples of both 3 and 5 don’t get double-counted in the sum.

As pointed out in the Project Euler solution overview for the problem, it’s simpler to first find the sum of the multiples of 3, then find the sum of the multiples of 5, add those sums, and then subtract the amount that has been double-counted.

How do you know how much to subtract? Well, if a number is divisible by both 3 and 5, then it must be divisible by the product of 3 x 5, 15. So the multiples of 15 are the numbers that show up both as multiples of 3 and as multiples of 5. The sum of the multiples of 15 is the amount we need to subtract in order to compensate for duplicates.

Now we can write a much more elegant solution:

```val end = 1000

fun sumOfMultiples(num: Int) = (num until end step num).sum()

fun main() {
println(sumOfMultiples(3) + sumOfMultiples(5) - sumOfMultiples(15))
}```
Kotlin language notes
• `fun sumOfMultiples(num: Int) = ...` defines a function that takes an integer parameter and returns the result of evaluating the expression on the right side of the equals sign. It's a shorthand that is equivalent to this:
```fun sumOfMultiples(num: Int): Int {
return (num until end step num).sum()
}```
• `(num until end step num)` gets a list of numbers starting at `num` and incrementing by `num` for as long as the number is less than `end`. So when `num` is 3, it finds 3, 6, 9, 12, etc.

## Solution 5: Efficient sum of multiples function

All of the above solutions work fine for finding the sum of multiples one thousand, or even one billion. Try finding the multiples below one trillion, though, and they’ll take a long time.

As described in the Project Euler solution overview for the problem, there is a much more efficient approach.

The sum of multiples of 3 that are less than 10 can be written as:

3 + 6 + 9

This is equivalent to:

(3 * 1) + (3 * 2) + (3 * 3)

Which is equivalent to:

3 * (1 + 2 + 3)

More generally, the sum of the first N multiples of 3 is:

3 * (1 + 2 + 3 + … + N)

There’s a simple formula for calculating the sum `(1 + 2 + 3 + ... + N)` directly: `(N * (N + 1)) / 2`. So, the sum of the first N multiples of 3 is:

3 * (N * (N + 1)) / 2

If we change our `sumOfMultiples` function from solution 4 to use this instead of looping over a bunch of numbers, it’ll be much faster. To do this, we need to know N. N is just the number of multiples of 3 that are less than whatever our limit is (1000 in the original Euler problem). That’s equivalent to the number of times that the largest number less than the limit can be divided evenly by three. So, all we have to do is subtract 1 from the limit, divide by 3, discard the remainder, and plug the result into the above formula.

Here’s the code:

```val end = 1000000000000L

fun sumOfMultiples(num: Long): Long {
val terms = (end - 1) / num
return num * terms * (terms + 1) / 2
}

fun main() {
println(sumOfMultiples(3) + sumOfMultiples(5) - sumOfMultiples(15))
}```
Kotlin language notes
• The `L` at the end of `1000000000000L` indicates that the number should be stored as a `Long` instead of an `Int`. `Int`s can only hold numbers between -2^31=-2,147,483,648 and 2^31-1=2,147,483,647. `Long`s can hold numbers between -2^63=-9,223,372,036,854,775,808 and 2^63-1=9,223,372,036,854,775,807. The parameter and return types of `sumOfMultiples` were also changed to support `Long`s. You'd need to make similar changes in the other solutions if you wanted to test them with very large numbers.

This solution finishes practically instantly even for an input of one trillion.