Project Euler Problem 1: Mathematical Solution

Problem

Find the sum of all multiples of 3 or 5 below 1000.

Foundation: Arithmetic Series

Sum of 1 + 2 + 3 + ... + n:

$S_n = \frac{n(n+1)}{2}$

Proof (Gauss's method):

S_n =   1  +  2  +  3  + ... + n
S_n =   n  + n-1 + n-2 + ... + 1
────────────────────────────────
2S_n = n+1 + n+1 + n+1 + ... + n+1  (n times)

Therefore: $2S_n = n(n+1)$, so $S_n = \frac{n(n+1)}{2}$

Sum of multiples of m below N:

Multiples: m, 2m, 3m, ..., km where $k = \lfloor\frac{N-1}{m}\rfloor$

$\sum_{i=1}^{k} im = m \cdot \frac{k(k+1)}{2}$

Inclusion-Exclusion Principle

Let A = multiples of 3, B = multiples of 5

We want: $\sum_{n \in A \cup B} n$

Key insight: Elements in both A and B are multiples of lcm(3,5) = 15

$\sum_{A \cup B} = \sum_{A} + \sum_{B} - \sum_{A \cap B}$

Why subtract? Numbers divisible by both 3 and 5 get counted twice.

Calculation

Multiples of 3:

• Count: $k_3 = \lfloor 999/3 \rfloor = 333$
• Sum: $3 \cdot \frac{333 \cdot 334}{2} = 166,833$

Multiples of 5:

• Count: $k_5 = \lfloor 999/5 \rfloor = 199$
• Sum: $5 \cdot \frac{199 \cdot 200}{2} = 99,500$

Multiples of 15:

• Count: $k_{15} = \lfloor 999/15 \rfloor = 66$
• Sum: $15 \cdot \frac{66 \cdot 67}{2} = 33,165$

Final answer: $166,833 + 99,500 - 33,165 = 233,168$

Why This Works

1. Arithmetic series formula converts O(n) addition into O(1) formula
2. Inclusion-exclusion handles the overlap between sets
3. LCM property: When gcd(a,b)=1, numbers divisible by both a and b are exactly those divisible by a·b

General Formula

For divisors a, b with limit N:

$\text{Sum} = \frac{a \cdot k_a(k_a+1)}{2} + \frac{b \cdot k_b(k_b+1)}{2} - \frac{ab \cdot k_{ab}(k_{ab}+1)}{2}$

where $k_m = \lfloor(N-1)/m\rfloor$

Project Euler Problem 1: Programming Solution

As we have explained mathematically, the sum of all multiples of 3 or 5 below 1000 can be computed efficiently using arithmetic series and the inclusion-exclusion principle. However, we can also solve this problem using a simple programming approach (brute-force method).

#include <stdio.h>

long long sum_multiples(int k, int N)
{
    long long n = (N - 1) / k;
    return k * n * (n + 1) / 2;
}

// Why n = (N - 1) / k?
// We want multiples of k below N, so the largest multiple is k * n < N
// Thus, n = floor((N - 1) / k)

int main()
{
    int N = 1000;
    long long sum_3 = sum_multiples(3, N);
    long long sum_5 = sum_multiples(5, N);
    long long sum_15 = sum_multiples(15, N); // lcm(3, 5) = 15

    long long result = sum_3 + sum_5 - sum_15; // Inclusion-Exclusion
    printf("Sum of all multiples of 3 or 5 below %d is: %lld\n", N, result);
    return 0;
}

package main

import (
    "fmt"
)

func sumMultiples(k, N int) int64 {
    n := (N - 1) / k
    return int64(k) * int64(n) * int64(n+1) / 2
}

func main() {
    N := 1000
    sum3 := sumMultiples(3, N)
    sum5 := sumMultiples(5, N)
    sum15 := sumMultiples(15, N) // lcm(3, 5) = 15

    result := sum3 + sum5 - sum15 // Inclusion-Exclusion
    fmt.Printf("Sum of all multiples of 3 or 5 below %d is: %d\n", N, result)
}

fn sum_multiples(k: i64, n: i64) -> i64 {
    let m = (n - 1) / k;
    k * m * (m + 1) / 2
}

fn main() {
    let n = 1000;
    let sum_3 = sum_multiples(3, n);
    let sum_5 = sum_multiples(5, n);
    let sum_15 = sum_multiples(15, n); // lcm(3, 5) = 15

    let result = sum_3 + sum_5 - sum_15; // Inclusion-Exclusion
    println!("Sum of all multiples of 3 or 5 below {} is: {}", n, result);
}