950 Fundamental

950 Sum Of Multiples

Functional Programming

Tutorial

The Problem

Find the sum of all unique multiples of any factor in a given set, below a limit. For example, the sum of all multiples of 3 or 5 below 1000 is the classic Project Euler problem 1. Implement three approaches: iterator-based deduplication via HashSet, a fold-based functional accumulation, and an O(1) mathematical formula using inclusion-exclusion with GCD/LCM.

🎯 Learning Outcomes

• Generate multiples using (f..limit).step_by(f) for each factor

• Deduplicate across factors with HashSet<u64> — collect all multiples then sum

• Express the same logic as a fold that inserts into a HashSet incrementally

• Implement the closed-form formula: sum_divisible(k, limit) = k * n*(n+1)/2 where n = (limit-1)/k

• Apply inclusion-exclusion via GCD/LCM to avoid double-counting in the math version

Code Example

use std::collections::HashSet;

pub fn sum_of_multiples(factors: &[u64], limit: u64) -> u64 {
    factors
        .iter()
        .filter(|&&f| f != 0)
        .flat_map(|&f| (f..limit).step_by(f as usize))
        .collect::<HashSet<u64>>()
        .into_iter()
        .sum()
}

module IS = Set.Make(Int)

let sum_of_multiples factors limit =
  List.fold_left (fun s factor ->
    if factor = 0 then s
    else
      let multiples = List.init ((limit - 1) / factor) (fun i -> factor * (i + 1)) in
      List.fold_left (fun s m -> IS.add m s) s multiples
  ) IS.empty factors
  |> IS.fold (+) |> fun f -> f 0

Key Differences

Aspect	Rust	OCaml
Deduplication	`HashSet` — O(1) insert/lookup	`Set.Make(Int)` — O(log n) insert
Range generation	`(f..limit).step_by(f)` — iterator	Recursive `go` function
Union	Implicit via `HashSet` collect	`IntSet.union`
Math formula	Feasible with explicit GCD/LCM	Same algorithm

step_by is the idiomatic way to generate arithmetic sequences in Rust. The HashSet approach is simpler for moderate inputs; the mathematical formula is O(factors²) and works for arbitrarily large limits.

OCaml Approach

module IntSet = Set.Make(Int)

let multiples_below f limit =
  let rec go acc m =
    if m >= limit then acc
    else go (IntSet.add m acc) (m + f)
  in
  if f = 0 then IntSet.empty else go IntSet.empty f

let sum_of_multiples factors limit =
  let all_multiples =
    List.fold_left
      (fun acc f -> IntSet.union acc (multiples_below f limit))
      IntSet.empty factors
  in
  IntSet.fold ( + ) all_multiples 0

OCaml's Set.Make(Int) provides an ordered set backed by a balanced BST. IntSet.union combines the multiples from each factor, naturally deduplicating. The fold over IntSet sums the elements.

Full Source

#![allow(clippy::all)]
use std::collections::HashSet;

pub fn sum_of_multiples(factors: &[u64], limit: u64) -> u64 {
    factors
        .iter()
        .filter(|&&f| f != 0)
        .flat_map(|&f| (f..limit).step_by(f as usize))
        .collect::<HashSet<u64>>()
        .into_iter()
        .sum()
}

pub fn sum_of_multiples_fold(factors: &[u64], limit: u64) -> u64 {
    let set: HashSet<u64> =
        factors
            .iter()
            .filter(|&&f| f != 0)
            .fold(HashSet::new(), |mut acc, &f| {
                (f..limit).step_by(f as usize).for_each(|m| {
                    acc.insert(m);
                });
                acc
            });
    set.into_iter().sum()
}

fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn lcm_pair(a: u64, b: u64) -> u64 {
    a / gcd(a, b) * b
}

pub fn sum_of_multiples_math(factors: &[u64], limit: u64) -> u64 {
    fn sum_divisible(k: u64, limit: u64) -> u64 {
        if k == 0 {
            return 0;
        }
        let n = (limit - 1) / k;
        k * n * (n + 1) / 2
    }

    let unique: Vec<u64> = {
        let mut seen = HashSet::new();
        factors
            .iter()
            .filter(|&&f| f != 0 && seen.insert(f))
            .copied()
            .collect()
    };

    let n = unique.len();
    (1u64..=(1 << n) - 1)
        .map(|mask| {
            let mut lcm = 1u64;
            let mut bits = 0u32;
            for (i, &val) in unique.iter().enumerate() {
                if mask & (1 << i) != 0 {
                    bits += 1;
                    lcm = lcm_pair(lcm, val);
                    if lcm >= limit {
                        return 0i64;
                    }
                }
            }
            let s = sum_divisible(lcm, limit) as i64;
            if bits % 2 == 1 {
                s
            } else {
                -s
            }
        })
        .sum::<i64>() as u64
}

/* Output:
   sum_of_multiples([3, 5], 1000)          = 233168
   sum_of_multiples([2,3,5,7,11], 10000)   = 39614537
   sum_of_multiples([], 1000)               = 0
   sum_of_multiples([0, 3], 10)             = 18

   -- fold variant --
   sum_of_multiples_fold([3, 5], 1000)      = 233168

   -- math (inclusion-exclusion) variant --
   sum_of_multiples_math([3, 5], 1000)      = 233168
   sum_of_multiples_math([2,3,5,7,11],10000)= 39614537
*/

module IS = Set.Make(Int)

let sum_of_multiples factors limit =
  List.fold_left (fun s factor ->
    if factor = 0 then s
    else
      let multiples = List.init ((limit - 1) / factor) (fun i -> factor * (i + 1)) in
      List.fold_left (fun s m -> IS.add m s) s multiples
  ) IS.empty factors
  |> IS.fold (+) |> fun f -> f 0

let () =
  assert (sum_of_multiples [3; 5] 1000 = 233168);
  assert (sum_of_multiples [2; 3; 5; 7; 11] 10000 = 23331668);
  assert (sum_of_multiples [] 1000 = 0);
  assert (sum_of_multiples [0; 3] 10 = 18);
  Printf.printf "%d\n" (sum_of_multiples [3; 5] 1000);
  Printf.printf "%d\n" (sum_of_multiples [2; 3; 5; 7; 11] 10000);
  print_endline "ok"

Deep Comparison

OCaml vs Rust: Sum of Multiples

Side-by-Side Code

OCaml

module IS = Set.Make(Int)

let sum_of_multiples factors limit =
  List.fold_left (fun s factor ->
    if factor = 0 then s
    else
      let multiples = List.init ((limit - 1) / factor) (fun i -> factor * (i + 1)) in
      List.fold_left (fun s m -> IS.add m s) s multiples
  ) IS.empty factors
  |> IS.fold (+) |> fun f -> f 0

Rust (idiomatic)

use std::collections::HashSet;

pub fn sum_of_multiples(factors: &[u64], limit: u64) -> u64 {
    factors
        .iter()
        .filter(|&&f| f != 0)
        .flat_map(|&f| (f..limit).step_by(f as usize))
        .collect::<HashSet<u64>>()
        .into_iter()
        .sum()
}

Rust (functional/fold — mirrors OCaml structure)

pub fn sum_of_multiples_fold(factors: &[u64], limit: u64) -> u64 {
    let set: HashSet<u64> =
        factors
            .iter()
            .filter(|&&f| f != 0)
            .fold(HashSet::new(), |mut acc, &f| {
                (f..limit).step_by(f as usize).for_each(|m| {
                    acc.insert(m);
                });
                acc
            });
    set.into_iter().sum()
}

Rust (mathematical — inclusion-exclusion, no set needed)

pub fn sum_of_multiples_math(factors: &[u64], limit: u64) -> u64 {
    fn sum_divisible(k: u64, limit: u64) -> u64 {
        let n = (limit - 1) / k;
        k * n * (n + 1) / 2
    }
    // ... inclusion-exclusion over all 2^k non-empty subsets via LCM
}

Type Signatures

Concept	OCaml	Rust
Function signature	`val sum_of_multiples : int list -> int -> int`	`fn sum_of_multiples(factors: &[u64], limit: u64) -> u64`
Factor list	`int list`	`&[u64]` (borrowed slice)
Set type	`IS.t` (balanced BST via `Set.Make(Int)`)	`HashSet<u64>` (hash table)
Empty set	`IS.empty`	`HashSet::new()`
Insert	`IS.add m s`	`acc.insert(m)`
Fold / reduce	`IS.fold (+)`	`.into_iter().sum()`
Sequence generation	`List.init n (fun i -> f*(i+1))`	`(f..limit).step_by(f)`

Key Insights

Set deduplication is the core idea. Both OCaml and Rust use a set to ensure each multiple is counted only once, regardless of how many factors produce it. This is the direct translation: Set.Make(Int) → HashSet<u64>.

Lazy vs eager sequences. OCaml's List.init eagerly allocates a list of multiples. Rust's range + step_by is a lazy iterator — it produces values on demand, with no intermediate allocation until collect.

Mutable accumulator in fold. OCaml's functional sets are immutable: each IS.add returns a new set. The Rust fold variant uses |mut acc, ...| { acc.insert(...); acc } — the mut acc binding allows in-place mutation of the HashSet while still following the fold signature, blending functional form with imperative efficiency.

**step_by replaces List.init arithmetic.** The OCaml expression List.init ((limit-1)/factor) (fun i -> factor * (i+1)) computes multiples manually. In Rust, (factor..limit).step_by(factor) expresses the same arithmetic progression directly using the iterator's built-in stepping mechanism.

Mathematical alternative avoids O(limit) space. The inclusion-exclusion solution uses sum(k below N) = k * n*(n+1)/2 over LCM of every subset — O(2^k) time, O(k) space. This showcases how understanding the mathematical structure can eliminate data structures entirely, a pattern common in competitive programming.

When to Use Each Style

Use idiomatic Rust (flat_map + HashSet) when: you want clarity and correctness with moderate-sized inputs; the code reads naturally as "collect all multiples, deduplicate, sum".

Use fold-based Rust when: you want to mirror the OCaml structure closely for pedagogical comparison, or when you need to interleave set construction with other per-factor logic.

Use mathematical inclusion-exclusion when: the limit is very large (billions) making O(limit) space impractical, or when factors are few (k ≤ 20) and you need O(1) space with a fast closed-form answer.

Exercises

Implement the inclusion-exclusion formula for exactly two factors.

Generalize inclusion-exclusion for n factors using the 2^n subsets approach.

Compute the sum of multiples of all primes below 20, under the limit 1,000,000, and compare the HashSet and formula approaches for speed.

Modify the function to accept a list of ranges (start, step) rather than single factors.

Write a property test verifying that all three implementations (iterator, fold, math) agree for random inputs.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust