954 Intermediate GitHub

954 Perfect Numbers

Functional Programming

Tutorial

The Problem

Classify integers as perfect, abundant, or deficient based on their aliquot sum (sum of proper divisors). A perfect number equals its aliquot sum (6 = 1+2+3), abundant exceeds it (12 > 1+2+3+4+6), and deficient falls short (8 < 1+2+4). Implement three variants of sum_of_divisors: brute-force filter, optimized square-root scan, and a flat_map divisor-pair version.

🎯 Learning Outcomes

• Compute aliquot sum with (1..n).filter(|&d| n.is_multiple_of(d)).sum()

• Classify using sum.cmp(&n) matched against Ordering::Equal/Greater/Less

• Optimize to O(√n) by iterating i up to sqrt(n) and including both i and n/i

• Implement a flat_map version that generates divisor pairs (i, n/i) as an iterator

• Handle edge case: n=0 is Invalid; 1 has sum 0 (deficient)

Code Example

#![allow(clippy::all)]
/// Perfect Numbers — Classification
///
/// Ownership: All values are Copy integers and enums. No heap allocation.

#[derive(Debug, PartialEq)]
pub enum Classification {
    Perfect,
    Abundant,
    Deficient,
    Invalid,
}

pub fn sum_of_divisors(n: u64) -> u64 {
    (1..n).filter(|&d| n.is_multiple_of(d)).sum()
}

pub fn classify(n: u64) -> Classification {
    if n == 0 {
        return Classification::Invalid;
    }
    let s = sum_of_divisors(n);
    match s.cmp(&n) {
        std::cmp::Ordering::Equal => Classification::Perfect,
        std::cmp::Ordering::Greater => Classification::Abundant,
        std::cmp::Ordering::Less => Classification::Deficient,
    }
}

/// Version 2: Optimized — only check up to sqrt(n)
pub fn sum_of_divisors_fast(n: u64) -> u64 {
    if n <= 1 {
        return if n == 1 { 0 } else { 0 };
    }
    let mut sum = 1u64; // 1 is always a proper divisor for n > 1
    let mut i = 2;
    while i * i <= n {
        if n.is_multiple_of(i) {
            sum += i;
            if i != n / i {
                sum += n / i;
            }
        }
        i += 1;
    }
    sum
}

/// Version 3: Iterator with flat_map for divisor pairs
pub fn sum_of_divisors_iter(n: u64) -> u64 {
    if n <= 1 {
        return if n == 1 { 0 } else { 0 };
    }
    (2..)
        .take_while(|&i| i * i <= n)
        .flat_map(|i| {
            if n.is_multiple_of(i) {
                if i == n / i {
                    vec![i]
                } else {
                    vec![i, n / i]
                }
            } else {
                vec![]
            }
        })
        .sum::<u64>()
        + 1 // 1 is always a divisor
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_perfect_6() {
        assert_eq!(classify(6), Classification::Perfect);
    }

    #[test]
    fn test_perfect_28() {
        assert_eq!(classify(28), Classification::Perfect);
    }

    #[test]
    fn test_abundant() {
        assert_eq!(classify(12), Classification::Abundant);
    }

    #[test]
    fn test_deficient() {
        assert_eq!(classify(7), Classification::Deficient);
    }

    #[test]
    fn test_zero() {
        assert_eq!(classify(0), Classification::Invalid);
    }

    #[test]
    fn test_one() {
        assert_eq!(classify(1), Classification::Deficient);
    }

    #[test]
    fn test_fast_matches_naive() {
        for n in 1..=1000 {
            assert_eq!(
                sum_of_divisors(n),
                sum_of_divisors_fast(n),
                "mismatch at n={}",
                n
            );
        }
    }
}

(* Perfect Numbers — Classification *)

type classification = Perfect | Abundant | Deficient | Invalid

(* Version 1: Simple divisor sum *)
let sum_of_divisors n =
  List.init (n - 1) (fun i -> i + 1)
  |> List.filter (fun d -> n mod d = 0)
  |> List.fold_left (+) 0

let classify n =
  if n <= 0 then Invalid
  else
    let s = sum_of_divisors n in
    if s = n then Perfect
    else if s > n then Abundant
    else Deficient

(* Version 2: Optimized with sqrt bound *)
let sum_of_divisors_fast n =
  if n <= 1 then (if n = 1 then 1 else 0)
  else
    let sum = ref 1 in
    let i = ref 2 in
    while !i * !i <= n do
      if n mod !i = 0 then begin
        sum := !sum + !i;
        if !i <> n / !i then sum := !sum + n / !i
      end;
      incr i
    done;
    !sum

let () =
  assert (classify 6 = Perfect);
  assert (classify 28 = Perfect);
  assert (classify 12 = Abundant);
  assert (classify 7 = Deficient);
  assert (classify (-1) = Invalid)

Key Differences

Aspect	Rust	OCaml
Divisibility	`n.is_multiple_of(d)`	`n mod d = 0`
Three-way compare	`Ordering::Equal/Greater/Less` via `.cmp()`	Chained `if/else if/else`
Iterator range	`(1..n)`	`List.init (n-1) (fun i -> i+1)`
Mutable fast version	`while` loop with mutable `i`	`ref` counters in `while`

Perfect numbers are rare: 6, 28, 496, 8128, 33550336. The O(√n) optimization is essential for classifying large numbers like 33,550,336 without waiting.

OCaml Approach

type classification = Perfect | Abundant | Deficient | Invalid

let sum_of_divisors n =
  if n <= 0 then 0
  else
    List.init (n - 1) (fun i -> i + 1)
    |> List.filter (fun d -> n mod d = 0)
    |> List.fold_left ( + ) 0

let classify n =
  if n = 0 then Invalid
  else
    let s = sum_of_divisors n in
    if s = n then Perfect
    else if s > n then Abundant
    else Deficient

(* Optimized *)
let sum_of_divisors_fast n =
  if n <= 1 then 0
  else
    let sum = ref 1 in
    let i = ref 2 in
    while !i * !i <= n do
      if n mod !i = 0 then begin
        sum := !sum + !i;
        if !i <> n / !i then sum := !sum + n / !i
      end;
      incr i
    done;
    !sum

OCaml's immutable List approach for the brute-force version mirrors the Rust iterator chain exactly. The optimized version uses OCaml's ref-based mutation (idiomatic for loops with mutable counters).

Full Source

#![allow(clippy::all)]
/// Perfect Numbers — Classification
///
/// Ownership: All values are Copy integers and enums. No heap allocation.

#[derive(Debug, PartialEq)]
pub enum Classification {
    Perfect,
    Abundant,
    Deficient,
    Invalid,
}

pub fn sum_of_divisors(n: u64) -> u64 {
    (1..n).filter(|&d| n.is_multiple_of(d)).sum()
}

pub fn classify(n: u64) -> Classification {
    if n == 0 {
        return Classification::Invalid;
    }
    let s = sum_of_divisors(n);
    match s.cmp(&n) {
        std::cmp::Ordering::Equal => Classification::Perfect,
        std::cmp::Ordering::Greater => Classification::Abundant,
        std::cmp::Ordering::Less => Classification::Deficient,
    }
}

/// Version 2: Optimized — only check up to sqrt(n)
pub fn sum_of_divisors_fast(n: u64) -> u64 {
    if n <= 1 {
        return if n == 1 { 0 } else { 0 };
    }
    let mut sum = 1u64; // 1 is always a proper divisor for n > 1
    let mut i = 2;
    while i * i <= n {
        if n.is_multiple_of(i) {
            sum += i;
            if i != n / i {
                sum += n / i;
            }
        }
        i += 1;
    }
    sum
}

/// Version 3: Iterator with flat_map for divisor pairs
pub fn sum_of_divisors_iter(n: u64) -> u64 {
    if n <= 1 {
        return if n == 1 { 0 } else { 0 };
    }
    (2..)
        .take_while(|&i| i * i <= n)
        .flat_map(|i| {
            if n.is_multiple_of(i) {
                if i == n / i {
                    vec![i]
                } else {
                    vec![i, n / i]
                }
            } else {
                vec![]
            }
        })
        .sum::<u64>()
        + 1 // 1 is always a divisor
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_perfect_6() {
        assert_eq!(classify(6), Classification::Perfect);
    }

    #[test]
    fn test_perfect_28() {
        assert_eq!(classify(28), Classification::Perfect);
    }

    #[test]
    fn test_abundant() {
        assert_eq!(classify(12), Classification::Abundant);
    }

    #[test]
    fn test_deficient() {
        assert_eq!(classify(7), Classification::Deficient);
    }

    #[test]
    fn test_zero() {
        assert_eq!(classify(0), Classification::Invalid);
    }

    #[test]
    fn test_one() {
        assert_eq!(classify(1), Classification::Deficient);
    }

    #[test]
    fn test_fast_matches_naive() {
        for n in 1..=1000 {
            assert_eq!(
                sum_of_divisors(n),
                sum_of_divisors_fast(n),
                "mismatch at n={}",
                n
            );
        }
    }
}

(* Perfect Numbers — Classification *)

type classification = Perfect | Abundant | Deficient | Invalid

(* Version 1: Simple divisor sum *)
let sum_of_divisors n =
  List.init (n - 1) (fun i -> i + 1)
  |> List.filter (fun d -> n mod d = 0)
  |> List.fold_left (+) 0

let classify n =
  if n <= 0 then Invalid
  else
    let s = sum_of_divisors n in
    if s = n then Perfect
    else if s > n then Abundant
    else Deficient

(* Version 2: Optimized with sqrt bound *)
let sum_of_divisors_fast n =
  if n <= 1 then (if n = 1 then 1 else 0)
  else
    let sum = ref 1 in
    let i = ref 2 in
    while !i * !i <= n do
      if n mod !i = 0 then begin
        sum := !sum + !i;
        if !i <> n / !i then sum := !sum + n / !i
      end;
      incr i
    done;
    !sum

let () =
  assert (classify 6 = Perfect);
  assert (classify 28 = Perfect);
  assert (classify 12 = Abundant);
  assert (classify 7 = Deficient);
  assert (classify (-1) = Invalid)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_perfect_6() {
        assert_eq!(classify(6), Classification::Perfect);
    }

    #[test]
    fn test_perfect_28() {
        assert_eq!(classify(28), Classification::Perfect);
    }

    #[test]
    fn test_abundant() {
        assert_eq!(classify(12), Classification::Abundant);
    }

    #[test]
    fn test_deficient() {
        assert_eq!(classify(7), Classification::Deficient);
    }

    #[test]
    fn test_zero() {
        assert_eq!(classify(0), Classification::Invalid);
    }

    #[test]
    fn test_one() {
        assert_eq!(classify(1), Classification::Deficient);
    }

    #[test]
    fn test_fast_matches_naive() {
        for n in 1..=1000 {
            assert_eq!(
                sum_of_divisors(n),
                sum_of_divisors_fast(n),
                "mismatch at n={}",
                n
            );
        }
    }
}

Deep Comparison

Perfect Numbers — Comparison

Core Insight

Number classification shows how both languages handle three-way comparison. OCaml uses chained if/else; Rust can use match on Ordering for a more structured approach. The optimized sqrt version shows imperative style in both languages.

OCaml Approach

• List.init (n-1) (fun i -> i+1) creates candidate divisors

• List.filter + List.fold_left (+) 0 for sum

• Chained if s = n then ... else if s > n then ...

• Optimized version uses ref for mutable state (imperative OCaml)

Rust Approach

• (1..n).filter().sum() — lazy range, no list allocation

• s.cmp(&n) returns Ordering — match on Equal/Greater/Less

• while i * i <= n loop for optimized version

• flat_map iterator version for functional sqrt approach

Comparison Table

Aspect	OCaml	Rust
Range	`List.init (n-1)` (allocates)	`(1..n)` (lazy)
Three-way	`if/else if/else`	`match s.cmp(&n)`
Mutable loop	`ref` + `while`	`let mut` + `while`
Invalid	`n <= 0`	`n == 0` (u64 can't be negative)
Sum	`List.fold_left (+) 0`	`.sum()`

Learner Notes

• u64 means no negative numbers — Invalid only needs to check zero

• std::cmp::Ordering makes three-way comparisons explicit and exhaustive

• The sqrt optimization reduces O(n) to O(√n) — important for large numbers

• flat_map with vec![] in iterators is less efficient than the while loop

Exercises

Implement find_perfect_numbers(limit) that returns all perfect numbers up to the limit.

Verify that all even perfect numbers follow the Euclid-Euler form 2^(p-1) * (2^p - 1) for Mersenne prime 2^p - 1.

Use the O(√n) version to classify all numbers from 1 to 10,000 and count how many are perfect, abundant, and deficient.

Implement is_amicable(n) — n and m are amicable if sum_of_divisors(n) == m and sum_of_divisors(m) == n (and n ≠ m).

Extend the flat_map divisor-pair version to also compute the product of all proper divisors.

Open Source Repos

functional-rust

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

Rust