Efficient Algorithm for Sum of Multiples

Find the Jupyter solution here:

When solving programming challenges, there's often a wide gap between the obvious solution and the optimal one. This gap represents not just efficiency, but also mathematical insight. Today, we'll explore one such problem:

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 a given number n.

This seemingly simple problem can teach us important lessons about algorithmic efficiency.

The Obvious Approach: O(n) Solution

The most intuitive solution is to iterate through each number below n, check if it's divisible by 3 or 5, and add it to our running total if it is:

This works perfectly well for small inputs. For n = 10, it quickly gives us 23. But what about when n becomes very large? The time complexity is O(n), meaning the execution time grows linearly with the input size.

Mathematical Optimization: O(1) Solution

Is there a more efficient way? Indeed, there is. We can solve this in constant time O(1) using a mathematical formula, regardless of how large n becomes.

Deriving the Formula

Let's find a formula for the sum of all multiples of a number k that are less than n.

The multiples of k less than n can be written as:
k, 2k, 3k, ..., p·k

Where p is the largest integer such that p·k < n.

The sum S can be written as:
S = k·(1 + 2 + 3 + ... + p)

The sum of the first p natural numbers is given by the formula:
1 + 2 + 3 + ... + p = p(p+1)/2

So our formula becomes:
S = k · p(p+1)/2

To find p, we can use:
p = ⌊(n-1)/k⌋

Where ⌊x⌋ represents the floor function (the greatest integer less than or equal to x).

Implementation

With this formula, we can implement a function to calculate the sum of multiples of any number k below n:

Handling the Overlap

However, we can't simply add the sum of multiples of 3 and the sum of multiples of 5, because numbers like 15, 30, 45, etc. would be counted twice. These are the multiples of both 3 and 5, which are the multiples of their least common multiple (LCM) - in this case, 15.

The inclusion-exclusion principle from set theory gives us the formula:
Sum of multiples of 3 or 5 = Sum of multiples of 3 + Sum of multiples of 5 - Sum of multiples of 15

Final Solution

Performance Comparison

For small inputs, the performance difference between the O(n) and O(1) solutions is negligible. But as n grows larger, the difference becomes dramatic.

For n = 1,000,000:

• The O(n) solution needs to perform 1 million iterations
• The O(1) solution performs only a few arithmetic operations

This example demonstrates how mathematical insight can transform an algorithm from linear to constant time — a significant improvement for large inputs.

Real-World Application

This type of mathematical optimization is valuable in many computing scenarios:

• Processing large datasets
• Time-critical applications
• Resource-constrained environments
• Competitive programming

Conclusion

The problem of finding the sum of multiples of 3 and 5 illustrates a fundamental principle in algorithm design: mathematical insight often leads to more efficient solutions than brute force approaches.

When faced with algorithmic challenges, it's worth asking:
"Is there a mathematical pattern or formula that can solve this more efficiently?"

Sometimes, a deep understanding of mathematics can transform an O(n) solution into an O(1) solution — making your algorithm not just faster, but more elegant.

Remember: efficiency in algorithms isn't just about optimization; it's about finding the right approach to the problem.