001 - Multiples of 3 or 5

Overview

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.

Solution

def solution(limit: int = 1000) -> int:
    target = limit - 1
 
    def sum_multiples_of(k: int) -> int:
        n = target // k
        return (n * (k + (n * k))) // 2
 
    return sum_multiples_of(3) + sum_multiples_of(5) - sum_multiples_of(15)

Benchmarks

======================================================================
🕵️  AUDITING PROJECT EULER ARCHITECTURE: solution()
======================================================================
Result Yielded         : 233168
Average Execution Time : 1.68 microseconds
Peak Memory Allocated  : 0.40 KB
Algorithmic Scaling    : 1.60x time growth on 10x input
======================================================================

The Mathematical Rationale

1. Arithmetic Progressions (AP)

Multiples of any number k form an arithmetic progression—a sequence of numbers where the difference between consecutive terms is constant. For example, the multiples of 3 below 20 are: 3, 6, 9, 12, 15, 18.

The sum of an arithmetic progression can be calculated instantly using the standard summation formula:

S_n = (n / 2) × (a₁ + a_n)

Where:

n is the total number of terms.
a₁ is the first term (which is always k).
a_n is the last term in the sequence below the limit (which can be written as n × k).

2. Finding the Number of Terms (n)

To find how many multiples of k exist below a strict target limit, we use integer division:

n = ⌊ target / k ⌋

Substituting a₁ = k and a_n = n × k back into the summation formula yields an efficient simplified equation:

S_n = [n × (k + (n × k))] / 2

Handling Overlaps: The Inclusion-Exclusion Principle

If we simply add the sum of all multiples of 3 to the sum of all multiples of 5, we encounter a double-counting problem. Numbers that are multiples of both 3 and 5 (i.e., multiples of 15, like 15, 30, 45, etc.) are included in both sets.

To correct for this, we apply the Inclusion-Exclusion Principle:

Total Sum = Sum(3) + Sum(5) - Sum(15)

By subtracting the sum of the multiples of 15 once, we neutralize the duplicate tracking and arrive at the exact mathematical total.

Complexity Analysis

Metric	Linear Loop Approach	Constant AP Framework
Time Complexity	O(N)	O(1)
Space Complexity	O(1)	O(1)
Execution Scaling	Scales directly with the input size.	Requires exactly 3 function evaluations regardless of input size.

ആരാമം

Explorer