Breaking Down Project Euler #1: Multiples of 3 and 5

Greetings, friends.

If you want to get to the meat of this post, click here

As you may (or may not) know, I'm a currently unemployed software developer. A currently unemployed workaholic of a software developer. A currently unemployed workaholic of a software developer who did not spec into the mathematics skill tree.

For a long time, I lived with this mistaken belief that people were either good at math or they were not good at math, and I was clearly a member of the latter group. Until I was talking to one of my best friends, the smartest man I've ever met¹, about my terrible-at-math affliction.

Paraphrased version of the conversation:

"No one's good at math to start with."
"But you're good at math!"
".... because I went to a library every day and read everything I could about it. And practiced. A lot. And asked a lot of questions. I was rubbish at math."
"But you're an electrical engineer!"
"Exactly. If I can learn it, so can you. You just have to want to."

Damn it, I thought to myself. So this was exactly like that whole "no one's an amazing artist without practice" things. I have no one to blame but myself.²

Why am I telling you this story? Well, dear, patient reader, I'm a workaholic out of work. I know that if I want to stop being a workaholic out of work, I should spec more into the whiteboarding skill tree. While everyone's approach for leveling up on this skill tree is different, my general approach tends to be to try to solve a lot of problems on HackerRank/LeetCode/whatever other platform I happen to have open at the time. Emphasis on try. It would be lying to say that I struggle with every algorithmic question, because I have familiarity with quite a few now. I've slain those dragons, they hold no power over me, I am victorious. But for others, I just ... can't. For some problems, I can't even come up with a terrible solution to a problem.³ For still others, I can come up with the naive approach for solving it, but inevitably some of the tests on whatever the platform is are smart enough to test for poorly performing code and will error out.

So what do I, a workaholic with a stubborn streak and a deep hatred of not understanding a problem, do?

I look at solutions. Sometimes, the solutions are straightforward and I feel like an idiot for not having thought of approaching it that way, before reminding myself that everything always seems easier with hindsight. Other times, the solutions work, but I am confused either a) how or b) why. And then I spend an embarrassing amount of time trying to figure out the how and why.

Which brings us to this post!

Multiples of 3 and 5

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 naive approach to this problem is fairly straightforward if you are familiar with the modulo operator, which gives you the remainder when one number is divided by another. One approach might be:

• initialize a variable sum with the value of 0
• iterate from 3 to 999 (3 because you know 1 and 2 don't divide cleanly)
• if the number is divisible by 3 or 5, add that number to the sum
• return the sum

function sumOf3or5(num) {
    let sum = 0;
    for (let i = 3; i < num; i++) {
        if (i % 3 === 0 || i % 5 === 0) {
            sum += i;
        }
    }
    return sum;
}

But the tests were tricky. They used values greater than Number.MAX_SAFE_INTEGER, which meant that when it came to mathematical operations on those numbers ... well, it didn't do well. But more than that, because the numbers were so high, it also meant that this naive solution was not going to work⁴.

This was one of the times where I had to look at other people's solutions to come to an answer. The solution I ended up with was:

function sumOf3or5(num) {
/* 
    The test cases use numbers greater than Math.MAX_INTEGER, so we 
    need to use a data type that can handle larger numbers.  You could 
    pull in a library like bignumbers.js for this, but there's a new data 
    type in JavaScript for big numbers -- BigInt.   
*/
    num = BigInt(num);
/*
    We not only have to add the sum of multiples of 3 and 5 together, but 
    because 3 * 5 = 15, we need to make sure to subtract all the sums of 
    multiples of 15 in order to remove duplicates
*/
    return (
        BigInt(sumOfSequence(num - 1n, 3) 
        + sumOfSequence(num - 1n, 5)
        - sumOfSequence(num - 1n, 15)).toString()
        )
}

function sumOfSequence(num, multiple) {
    // find the number of times multiple can go into num
    let terms = num / BigInt(multiple);
    // Use Gauss's summation trick
    let sum = terms * (terms + 1n) / 2n;
    return BigInt(multiple) * sum;
}

First off, if you're not familiar with BigInt in JavaScript, that 'n' at the end of numbers is just to indicate that it's a BigInt type.

Second, I'm sure you're looking at that n * (n + 1) / 2 bit and going "...?"

"I get that that's the way to sum numbers, but why are we using the number of times a multiple can go into the number for the formula? And why are we multiplying by the multiple afterward?"

Good question.

Say that we're looking for the sum of multiples of 3s and 5s for numbers less than 10.

To calculate the multiples of 3, we would be passing 9 and 3 to our sumOfSequence function. That would mean that the 'n' we would be using for the summation would be 3 (9 / 3 = 3). So what we're using Gauss's trick for is the summation of 1 to 3 (1 + 2 + 3) and then multiplying it by the multiple so that we get the actual sum of the multiple.

(1 + 2 + 3) * 3 = 18
3 + 6 + 9 = 18

If you made it all the way down here, thanks for reading. I hope it helps you in some small way. Let me know if you'd be interested in reading more content like this. Honestly, feel free to reach out in general. Be safe, be kind, take care!

Every time I found myself leaning on my natural writing tendency of including an aside, I cut and pasted it down here into the footnotes.

Footnotes

_{[1] Literally a genius, and not in the pretentious "I'm a member of MENSA and all should bow before me" way, more in the "you asked a good question, but you would have to understand three different levels above what you currently know to understand my answer to your question, so let me patiently explain to you how all of that stuff works so you know what I'm talking about" way.
[2] Well, maybe my high school guidance counselor who convinced me to stop taking math because I would "never need it as a health and human sciences major". >insert an eyebrow narrow right here<
[3] Sometimes I can come up with a terrible solution, but it is so terrible that I wouldn't even admit to having come up with it. I'm serious, it's bad.
[4] It has to iterate through all of the numbers from 3 to the number passed in, so if the number is large, this is going to take a lot of time to execute.}