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.

Table of Contents:

• Solution 1: Brute force
• Solution 2: Functional-style brute force
• Solution 3: Loop over multiples
• Solution 4: Looping sum of multiples function
• Solution 5: Efficient sum of multiples function

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)
}

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)
}

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.

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))
}

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))
}

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