071 Fundamental

071 — Collatz Conjecture

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "071 — Collatz Conjecture" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. The Collatz conjecture (proposed by Lothar Collatz in 1937) states that iterating `f(n) = n/2` when n is even, or `f(n) = 3n+1` when n is odd, always eventually reaches 1, regardless of the starting value. Key difference from OCaml: 1. **Tail recursion**: The naive `1 + collatz(next)` is not tail

Tutorial

The Problem

The Collatz conjecture (proposed by Lothar Collatz in 1937) states that iterating f(n) = n/2 when n is even, or f(n) = 3n+1 when n is odd, always eventually reaches 1, regardless of the starting value. Despite being trivially stateable to a schoolchild, it has resisted proof by the best mathematicians for nearly 90 years. The sequence for n=27 takes 111 steps and reaches a peak of 9232 before eventually descending to 1. As of 2023, the conjecture has been verified computationally for all n up to approximately 2^68.

Paul Erdős famously said of the Collatz conjecture: "Mathematics is not yet ready for such problems." Its combination of simplicity and intractability makes it a favorite in recreational mathematics and computer science education.

As an engineering exercise, the Collatz sequence demonstrates: safe integer arithmetic with checked operations, recursive vs iterative implementation choices, the difference between computing a count (fold) and generating a sequence (unfold), and why Rust lacks tail-call optimization — making the iterative form the practical choice.

🎯 Learning Outcomes

• Implement Collatz step count using both direct recursion and a while loop

• Use Result<u64, String> to handle non-positive inputs safely at the API boundary

• Understand why iterative implementation is preferred in Rust — the language does not guarantee tail-call optimization

• Use std::iter::successors to generate the full Collatz sequence lazily as an iterator

• Distinguish "count steps" (returns a number) from "list steps" (returns a sequence) as different problem shapes

• Recognize that naive recursion is fragile for sequences of unknown bounded depth

Code Example

#![allow(clippy::all)]
/// Collatz Conjecture
///
/// Computing the 3n+1 sequence step count. Demonstrates simple recursion,
/// Result-typed safe API, and iterative variants.

/// Naive recursive — mirrors OCaml's version directly.
pub fn collatz_steps(n: u64) -> u64 {
    match n {
        1 => 0,
        n if n % 2 == 0 => 1 + collatz_steps(n / 2),
        n => 1 + collatz_steps(3 * n + 1),
    }
}

/// Safe API with Result — rejects non-positive inputs.
pub fn collatz(n: i64) -> Result<u64, String> {
    if n <= 0 {
        Err("Only positive integers are allowed".to_string())
    } else {
        Ok(collatz_steps(n as u64))
    }
}

/// Iterative version — idiomatic Rust, no recursion.
pub fn collatz_iter(n: i64) -> Result<u64, String> {
    if n <= 0 {
        return Err("Only positive integers are allowed".to_string());
    }
    let mut current = n as u64;
    let mut steps = 0u64;
    while current != 1 {
        current = if current.is_multiple_of(2) {
            current / 2
        } else {
            3 * current + 1
        };
        steps += 1;
    }
    Ok(steps)
}

/// Generate the full Collatz sequence.
pub fn collatz_sequence(n: u64) -> Vec<u64> {
    let mut seq = vec![n];
    let mut current = n;
    while current != 1 {
        current = if current.is_multiple_of(2) {
            current / 2
        } else {
            3 * current + 1
        };
        seq.push(current);
    }
    seq
}

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

    #[test]
    fn test_collatz_1() {
        assert_eq!(collatz(1), Ok(0));
    }

    #[test]
    fn test_collatz_6() {
        assert_eq!(collatz(6), Ok(8));
    }

    #[test]
    fn test_collatz_11() {
        assert_eq!(collatz(11), Ok(14));
    }

    #[test]
    fn test_collatz_27() {
        assert_eq!(collatz(27), Ok(111));
    }

    #[test]
    fn test_collatz_negative() {
        assert!(collatz(-1).is_err());
        assert!(collatz(0).is_err());
    }

    #[test]
    fn test_iter_matches_recursive() {
        for n in 1..=100 {
            assert_eq!(collatz(n), collatz_iter(n));
        }
    }

    #[test]
    fn test_sequence() {
        assert_eq!(collatz_sequence(6), vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }
}

let rec collatz_steps n =
  if n = 1 then 0
  else if n mod 2 = 0 then 1 + collatz_steps (n / 2)
  else 1 + collatz_steps (3 * n + 1)

let collatz n =
  if n <= 0 then Error "Only positive integers are allowed"
  else Ok (collatz_steps n)

let () =
  assert (collatz 1 = Ok 0);
  assert (collatz 6 = Ok 8);
  assert (collatz 27 = Ok 111);
  assert (collatz (-1) = Error "Only positive integers are allowed");
  print_endline "All assertions passed."

Key Differences

Tail recursion: The naive 1 + collatz(next) is not tail-recursive. OCaml's accumulator version aux next (acc + 1) is tail-recursive and safe. Rust's iterative version is equivalent.

**is_multiple_of**: Rust uses n.is_multiple_of(2) (stable since 1.72). OCaml uses n mod 2 = 0. Both express even-number check.

Integer overflow: 3n+1 can overflow u64 for large n. Rust's u64::checked_mul(3)?.checked_add(1)? detects overflow. OCaml's arbitrary-precision integers (with Zarith) avoid this.

**successors for sequence**: Rust's successors(Some(n), |&x| if x <= 1 { None } else { Some(step(x)) }) generates the sequence lazily — stopping when 1 is reached.

OCaml Approach

OCaml's naive version is not tail-recursive:

let rec collatz n =
  if n = 1 then 0
  else if n mod 2 = 0 then 1 + collatz (n / 2)
  else 1 + collatz (3 * n + 1)

The tail-recursive version uses an accumulator:

let collatz_iter n =
  let rec aux n acc =
    if n = 1 then acc
    else let next = if n mod 2 = 0 then n / 2 else 3 * n + 1
    in aux next (acc + 1)
  in aux n 0

OCaml guarantees TCO for tail-recursive functions, making the accumulator version stack-safe. Both forms exist in practice.

Full Source

#![allow(clippy::all)]
/// Collatz Conjecture
///
/// Computing the 3n+1 sequence step count. Demonstrates simple recursion,
/// Result-typed safe API, and iterative variants.

/// Naive recursive — mirrors OCaml's version directly.
pub fn collatz_steps(n: u64) -> u64 {
    match n {
        1 => 0,
        n if n % 2 == 0 => 1 + collatz_steps(n / 2),
        n => 1 + collatz_steps(3 * n + 1),
    }
}

/// Safe API with Result — rejects non-positive inputs.
pub fn collatz(n: i64) -> Result<u64, String> {
    if n <= 0 {
        Err("Only positive integers are allowed".to_string())
    } else {
        Ok(collatz_steps(n as u64))
    }
}

/// Iterative version — idiomatic Rust, no recursion.
pub fn collatz_iter(n: i64) -> Result<u64, String> {
    if n <= 0 {
        return Err("Only positive integers are allowed".to_string());
    }
    let mut current = n as u64;
    let mut steps = 0u64;
    while current != 1 {
        current = if current.is_multiple_of(2) {
            current / 2
        } else {
            3 * current + 1
        };
        steps += 1;
    }
    Ok(steps)
}

/// Generate the full Collatz sequence.
pub fn collatz_sequence(n: u64) -> Vec<u64> {
    let mut seq = vec![n];
    let mut current = n;
    while current != 1 {
        current = if current.is_multiple_of(2) {
            current / 2
        } else {
            3 * current + 1
        };
        seq.push(current);
    }
    seq
}

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

    #[test]
    fn test_collatz_1() {
        assert_eq!(collatz(1), Ok(0));
    }

    #[test]
    fn test_collatz_6() {
        assert_eq!(collatz(6), Ok(8));
    }

    #[test]
    fn test_collatz_11() {
        assert_eq!(collatz(11), Ok(14));
    }

    #[test]
    fn test_collatz_27() {
        assert_eq!(collatz(27), Ok(111));
    }

    #[test]
    fn test_collatz_negative() {
        assert!(collatz(-1).is_err());
        assert!(collatz(0).is_err());
    }

    #[test]
    fn test_iter_matches_recursive() {
        for n in 1..=100 {
            assert_eq!(collatz(n), collatz_iter(n));
        }
    }

    #[test]
    fn test_sequence() {
        assert_eq!(collatz_sequence(6), vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }
}

let rec collatz_steps n =
  if n = 1 then 0
  else if n mod 2 = 0 then 1 + collatz_steps (n / 2)
  else 1 + collatz_steps (3 * n + 1)

let collatz n =
  if n <= 0 then Error "Only positive integers are allowed"
  else Ok (collatz_steps n)

let () =
  assert (collatz 1 = Ok 0);
  assert (collatz 6 = Ok 8);
  assert (collatz 27 = Ok 111);
  assert (collatz (-1) = Error "Only positive integers are allowed");
  print_endline "All assertions passed."

✓ Tests Rust test suite

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

    #[test]
    fn test_collatz_1() {
        assert_eq!(collatz(1), Ok(0));
    }

    #[test]
    fn test_collatz_6() {
        assert_eq!(collatz(6), Ok(8));
    }

    #[test]
    fn test_collatz_11() {
        assert_eq!(collatz(11), Ok(14));
    }

    #[test]
    fn test_collatz_27() {
        assert_eq!(collatz(27), Ok(111));
    }

    #[test]
    fn test_collatz_negative() {
        assert!(collatz(-1).is_err());
        assert!(collatz(0).is_err());
    }

    #[test]
    fn test_iter_matches_recursive() {
        for n in 1..=100 {
            assert_eq!(collatz(n), collatz_iter(n));
        }
    }

    #[test]
    fn test_sequence() {
        assert_eq!(collatz_sequence(6), vec![6, 3, 10, 5, 16, 8, 4, 2, 1]);
    }
}

Deep Comparison

Collatz Conjecture: OCaml vs Rust

The Core Insight

The Collatz sequence is simple enough that both languages express it almost identically. The interesting comparison is in error handling: OCaml's Result type and Rust's Result<T, E> serve the same purpose but with different ergonomics around the ? operator and pattern matching.

OCaml Approach

OCaml uses if/else chains for the three cases (n=1, even, odd). The Result type (Ok/Error) wraps the safe API. Pattern matching on the result uses match ... with Ok s -> ... | Error e -> .... The recursive version relies on OCaml's guaranteed tail-call optimization for the else branches (though this particular recursion isn't strictly tail-recursive due to 1 + ...).

Rust Approach

Rust uses match with guards (n if n % 2 == 0 => ...) for cleaner pattern matching. The Result<u64, String> return type forces callers to handle errors. The iterative version with while current != 1 is more idiomatic Rust and avoids any stack concerns. The ? operator (not shown here) could propagate errors even more concisely in larger pipelines.

Side-by-Side

Concept	OCaml	Rust
Pattern match	`if n = 1 then ... else if ...`	`match n { 1 => ..., n if ... => ... }`
Error type	`(int, string) result`	`Result<u64, String>`
Safe API	`Ok (collatz_steps n)`	`Ok(collatz_steps(n as u64))`
Integer types	`int` (63-bit)	`u64` (explicit unsigned)
Iteration	Recursion (idiomatic)	`while` loop (idiomatic)

What Rust Learners Should Notice

• Match guards (n if n % 2 == 0) are Rust's way to add conditions to match arms — cleaner than nested if/else

• Result<u64, String> is the Rust equivalent of OCaml's (int, string) result — both force explicit error handling

• Rust's explicit integer types (u64 vs i64) make the domain constraint (positive integers) partially expressible in the type system

• The iterative version is preferred in Rust — it's clear, stack-safe, and often faster

• as u64 is an explicit cast — Rust never silently converts between integer types

Exercises

Longest sequence: Find the starting number below 1,000,000 with the longest Collatz sequence. Memoize intermediate results to avoid recomputation.

Stopping time distribution: Generate a histogram of Collatz stopping times for all n from 1 to 10,000. What is the mean, median, and maximum stopping time?

Syracuse problem variant: Instead of 3n+1, try 5n+1. Does it always reach 1? What about 3n+3? Experiment and observe.

Open Source Repos

functional-rust

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

Rust

Tutorial Video

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

Collatz Conjecture: OCaml vs Rust

The Core Insight

OCaml Approach

Rust Approach

Side-by-Side

What Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos