Problem #1 easy

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.

View on Project Euler

Implementations

#include <iostream>
int sum_natural_35(size_t upper)
{
  unsigned int sum(0);
  for( int i = upper ; --i; )
  {
    if( 0 == i % 3 )
    {
      sum += i;
    }
    else if ( 0 == i % 5 )
    {
      sum += i;
    }
  }
  return sum;
}

int main(int argc, char* argv[])
{
  std::cout << sum_natural_35(1000) << std::endl;
}

View on GitHub

O(n) time complexity

#!/usr/bin/env ruby
def euler001_solution
  sum = 0
  (0..999).each do |num|
    if num % 3 == 0 || num % 5 == 0
      sum += num
    end
  end
  sum
end

puts euler001_solution

View on GitHub

Solution Notes

Mathematical Background

This problem introduces the concept of finding multiples and summing them, which relates to arithmetic sequences. The inclusion-exclusion principle becomes relevant when dealing with numbers that are multiples of both 3 and 5 (i.e., multiples of 15).

The sum of multiples can be calculated using the formula for arithmetic series: $S = \frac{n(n+1)}{2} \times d$ where $n$ is the number of terms and $d$ is the common difference.

Algorithm Analysis

The implementations shown use a brute-force approach: iterate through all numbers below 1000 and sum those divisible by 3 or 5. This has O(n) time complexity where n = 1000.

A more efficient mathematical approach would use:

Sum of multiples of 3: $S_3 = 3 + 6 + 9 + \dots + 999 = 3(1 + 2 + 3 + \dots + 333) = 3 \times \frac{333 \times 334}{2}$
Sum of multiples of 5: $S_5 = 5 + 10 + 15 + \dots + 995 = 5(1 + 2 + 3 + \dots + 199) = 5 \times \frac{199 \times 200}{2}$
Sum of multiples of 15: $S_{15} = 15 + 30 + 45 + \dots + 990 = 15(1 + 2 + 3 + \dots + 66) = 15 \times \frac{66 \times 67}{2}$

Final sum: $S_3 + S_5 - S_{15}$ (inclusion-exclusion)

Time Complexity: O(n) for brute force (n=1000 iterations), O(1) for mathematical formula approach.
Space Complexity: O(1) - constant space regardless of input size.
Execution Time: Virtually instantaneous for both approaches, suitable for real-time computation.
Scalability: Brute force degrades linearly with n, mathematical approach remains constant time.

Key Insights

Numbers that are multiples of both 3 and 5 (like 15, 30, 45…) would be counted twice without proper handling
The mathematical approach is much more efficient for large limits
This problem teaches fundamental programming concepts: loops, conditionals, and modular arithmetic

Educational Value

This problem serves as an excellent introduction to Project Euler, teaching:

Basic programming constructs (loops and conditionals)
Modular arithmetic and divisibility
The importance of considering edge cases (multiples of both numbers)
The trade-off between simple iterative solutions and optimized mathematical formulas
How computational complexity affects solution choice

Carl Friedrich Gauss made significant contributions to arithmetic series and number theory.