090: Perfect Numbers — Classification

Difficulty: Beginner Category: Math / Recursion Concept: Number classification using sum of proper divisors Key Insight: Rust's `Ordering` enum and `cmp` method replace the if/else chain for three-way comparison, making the classification logic more explicit.

/// 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 % d == 0).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 % i == 0 {
            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 % i == 0 {
                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)

📊 Detailed 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