In this first problem, we will explore two approaches to solving this classic programming problem: finding the sum of all multiples of 3 or 5 below a certain limit. We will first implement a brute force solution and then optimize it using an arithmetic approach. We will also provide pseudo code for both solutions and show how they can be implemented in five different programming languages: C#, Rust, C++, F#, and Python.
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. Our goal is to find the sum of all the multiples of 3 or 5 below 1000.
In a brute force approach
initialize sum to 0
for each number i in the range 1 to 999:
if i is a multiple of 3 or i is a multiple of 5:
add i to the sum
print sum
The brute force solution iterates through all the numbers from 1 to 999 and checks if each number is a multiple of 3 or 5. If it is, it adds the number to the running sum. Finally, it prints the sum.
We have provided implementations of both the brute force and optimal solutions in five programming languages: C#, Rust, C++, F#, and Python. You can find the code for each language in the following gists:
Optimal Solution
The optimal solution uses arithmetic progressions to calculate the sum of multiples more efficiently. First, it defines a function sum_of_multiples that takes a divisor and a limit as arguments. The function calculates the number of times the divisor fits into the range up to the limit minus 1, and then computes the sum of all multiples using the formula for the sum of an arithmetic series.
Next, the code calculates the sum of multiples of 3, multiples of 5, and multiples of 15 (which are the common multiples of both 3 and 5) separately. Finally, it computes the total sum by adding the sums of 3s and 5s and subtracting the sum of 15s (to avoid counting them twice), and prints the total sum.
The optimal solution is better than the brute force solution because it significantly reduces the number of calculations by leveraging arithmetic progressions and the sum of arithmetic series formula. This approach eliminates the need to iterate through every number in the given range, resulting in a more computationally efficient solution that scales better with larger input values.
The formula for the sum of an arithmetic series is:
Sum = (n * (a1 + an)) / 2
where:
- n is the number of terms in the series,
- a1 is the first term of the series, and
- an is the last term of the series.
In the case of an arithmetic series with a common difference (d) between terms, the formula can also be written as:
Sum = n * (2 * a1 + (n - 1) * d) / 2
Instead of iterating through all the numbers up to the limit, we calculate the sum of multiples of 3, multiples of 5, and multiples of 15 (which are the common multiples of both 3 and 5) separately. We then add the sum of multiples of 3 and multiples of 5, and subtract the sum of multiples of 15 to avoid counting them twice. By doing this, we avoid unnecessary calculations, making the solution faster and more efficient, especially when dealing with larger limits.
The optimal solution works by cleverly using some math to calculate the sum of multiples more efficiently, rather than checking each number one by one. It takes advantage of the fact that the sum of an arithmetic series (a sequence of numbers with a constant difference between them, like 3, 6, 9, ...) can be calculated directly using a simple formula.
