Modular Arithmetic & Project Euler Problem One

In January 2020, which was approximately three years ago by my count, I happened to see this post:

I vaguely thought this sounded like a cool idea and that I should do it and write blog posts about it. I've chipped away at Project Euler before, and as of writing have solved about half of the first 100, although some through methods that I would be embarrassed to tout in a programming blog post.

A lot has happened since January, but I'm going to try Lindsey's 100 days of blogging in combination with this challenge:

I want to tell you straight up, right now, that we are absolutely not getting through the first 100 Project Euler problems in the next 100 days, but I want to start chipping away a bit each day and hopefully finish them all eventually. I am not planning to publish every day but stick with me.

Now, I also want to say by way of preface: these are puzzles that are fun to try yourself! There will be spoilers here, read at your own risk!

Also, Project Euler is pretty math-y. If that's not your thing, it's cool! There's plenty of programming that doesn't get this deep into math. And I'll try to bring in relevant programming and computer science concepts too when I can, because I'm not all about math either tbh

Okay, without further ado, problem one.

Find the sum of all the multiples of 3 or 5 below 1000.

This sounds similar to the classic FizzBuzz interview question and can be solved similarly.

The key idea here is that we need a way to quickly check whether a number is divisible by another number. We could do something like dividing the numbers and checking for figures after the decimal, but that seems arduous and might be annoying to ensure that the numbers are treated as decimals rather than automatically-rounded integers.

The magic here is the modulus operator. It may not have been covered in your math classes unless they covered discrete math or computer science, but the idea is pretty straightforward, it returns the remainder when the first number is divided by the second.

Here are a few examples:

10 % 5 == 0
23 % 5 == 3
4 % 5 == 4

If it's still unclear, try with a few more values in your REPL or on Repl.it.

Modular arithmetic comes up in plenty of applications irl, like minutes past the hour.

So we can see that numbers that are divisible by the second number will return zero with the modulus operator.

For numbers that are divisible by five:

i % 5 == 0

And for numbers that are divisible by three:

i % 3 == 0

Now that we have an easy way to identify these numbers, we can iterate through and add each of them to a running total. I wrote a function that would sum all 3 and 5 multiples under n, but there are plenty of alternate ways to approach it.

Here's my completed code, also available on GitHub.

def sumOf3or5MultiplesUnder(n):
    total = 0
    for i in range (0, n):
        if i % 3 == 0 or i % 5 == 0:
            total = total + i
    return total

print(sumOf3or5MultiplesUnder(1000))

That's it for problem one! Let me know what you think or if you used a different approach.