Multiples of 3 or 5 -

Premise

For any given number, we should compile a list of natural numbers that are multiples of either 3 or 5, followed by calculating their sum. As an illustration, if the provided number is 10, we would enumerate 3, 5, 6, and 9, and the total sum of these multiples is 23. Develop a method to determine the sum of all multiples up to 1000, and subsequently modify this method to compute the sum of multiples up to n. (NOTE: This is a Project Euler problem, and to the best of my knowledge, we are allowed to share solutions only for the first 100 problems, so I trust this is acceptable.)

Solution

Let us walk through one more brute-force example. Let us find all the multiples of 3 and 5 that sum up 20.

For 3 we have 3, 6, 9, 12, 15, 18, and for 5 we have 5, 10, 15 (not including 20). Something interesting happens here. A number appears twice in two sum series, namely 15. Adding it to the sum two times would be a mistake, so we can ignore one instance of it. We are summing 3, 5, 6, 9, 10, 12, 15, 18 and we get… 78.

Trying to generalize the solution we could write something like this below. S3 is the sum of all the multiples of 3 below 1000, S5 is the sum of all the multiples of 5 below 1000, and S15 is the sum of all the multiples of 15 below 1000. Why do we remove S15? Because we count them twice in S3 + S5.

S = S_{3} + S_{5} - S_{15}

What is the best way to mathematically represent these sums? We can represent them in terms of arithmetic progression.

S_{n} = \frac{n}{2} * (a_{1} + a_{n})

where S_n is the sum of the arithmetic progression, n is the number of total elements in the sequence, and a₁ and a_n denote the first and last term, respectively.

When it comes to the implementation, we can use the above formulas, or we can loop through the elements, check for the divisibility of the numbers, and sum them. Let us write both of those variations, in JS and Python.

JavaScript

function multiplesof3and5(limit) {
    const sumOf3 = getSum(3, limit);
    const sumOf5 = getSum(5, limit)
    const sumOf15 = getSum(15, limit)

    return sumOf3 + sumOf5 - sumOf15;
}

function getSum(lowerLimit, upperLimit) {
    const numberOfTerms = Math.floor(upperLimit / lowerLimit)
    return (numberOfTerms / 2) * (lowerLimit + numberOfTerms * lowerLimit)
    
}

console.log(multiplesof3and5(999))

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

console.log(multiplesof3and5(1000))

Python

def multiples_of_3_and_5(limit):
    sum_of_3 = get_sum(3, limit)
    sum_of_5 = get_sum(5, limit)
    sum_of_15 = get_sum(15, limit)

    return sum_of_3 + sum_of_5 - sum_of_15
    
def get_sum(low_limit, upper_limit):
    number_of_terms = upper_limit // low_limit
    return (number_of_terms / 2) * (low_limit + number_of_terms * low_limit)


print(multiples_of_3_and_5(999))

def multiples_of_3_and_5(limit):
    sum_result = 0
    for i in range(limit):
        if i % 3 == 0 or i % 5 == 0:
            sum_result += i
    return sum_result

print(multiples_of_3_and_5(1000))

Facebook Tweet Pin LinkedIn