Project Euler - Problem 1

Wednesday, April 23, 2025

I recently started a new blog series where I solve Project Euler problems and write about how I did it. This post addresses Problem 1.

So far, I’m sticking with the plan. Go me.

The GitHub repo is available here.

Anyway, let’s dive in.

The first problem states:

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.

The problem provides an example to start with. It shows how to find every number below 10 that’s a multiple of 3 or 5. Those are 3, 5, 6, and 9. Their sum is 23.

To solve the actual problem, we need to find every number below 1000 that is a multiple of 3 or 5. We can do 0 - 10 on paper (or in our heads). But calculating these numbers between 0 - 1000 is a little more time-consuming.

Luckily, we can solve this with a bit of programming.

My first solution

Here was my first solution.

func sumOfMultiples3And5(max: Int) -> Int {
    var sum: Int = 0

    for count in 1..<max {
        guard count % 3 == 0 || count % 5 == 0 else { continue }
        sum += count
    }

    return sum
}

This is a brute-force solution. It loops through every number from 1 to max, and if a number is divisible by 3 or 5, it adds it to a running sum.

My second solution

I then slightly rewrote the function. It’s still a brute-force approach. But it’s a little more concise.

func sumOfMultiples3And5(max: Int) -> Int {
    (1..<max)
        .filter { $0 % 3 == 0 || $0 % 5 == 0 }
        .reduce(0, +)
}

This approach does the same thing but in a more concise way.

It builds a range from 1 to max, filters out numbers that aren’t divisible by 3 or 5, and then adds the rest using reduce.

This approach is very concise but not as readable as my first approach.

My third solution

While I was writing this blog post, I discovered another approach. This is a purely mathematical approach.

This approach uses an Arithmetic Progression. Honestly, I won’t do a great job describing how this works. Instead, read through these two posts:

Here’s the code:

func sumOfMultiples3And5(max: Int) -> Int {
    let three = sumOfMultiplesUsingAP(multiple: 3, max: max)
    let five = sumOfMultiplesUsingAP(multiple: 5, max: max)
    let fifteen = sumOfMultiplesUsingAP(multiple: 15, max: max)

    return (three + five) - fifteen
}

// Using Arithmetic Progression
private func sumOfMultiplesUsingAP(multiple: Int, max: Int) -> Int {
    let numberOfMultiples = (max - 1) / multiple
    return multiple * numberOfMultiples * (numberOfMultiples + 1) / 2
}

This approach doesn’t use any looping. It’s much more efficient than the brute-force methods. But you need to know about Arithmetic Progressions and how to apply them.

If this were given to me in an interview, I would be satisfied with the brute-force solutions I came up with here. However, if the max number were larger than 1000, I would need to look for a more performant solution. The mathematical version would work well here.

Next up is problem two from the Project Euler website.

Older • Newer