Skip to content

Collatz Conjecture

Count the Collatz steps that take a positive integer to 1.

Adapted from Exercism’s problem specification (MIT). Listed under Numbers & Math.

// FILE: collatz_conjecture.nomi
//# Counts the steps of the Collatz conjecture that take a number to 1.

/// How many Collatz steps take `number` to 1: halve an even number, and
/// triple an odd one and add 1.
pub fn steps(number: Int) -> Result<Int, String>
    if number < 1 then return Err("Only positive integers are allowed")

    Iter.iterate(number, next)
    |> Iter.take_while(&(&1 != 1))
    |> Iter.count()
    |> Ok()
end

fn next(n: Int) -> Int
    if n % 2 == 0 then n / 2 else 3 * n + 1
end

// FILE: collatz_conjecture_test.nomi
import collatz_conjecture

test "counts the steps"
    [
        ("zero steps for one",                 1,       0),
        ("divide if even",                     16,      4),
        ("even and odd steps",                 12,      9),
        ("large number of even and odd steps", 1000000, 152),
    ]
    |> subtests (description, number, expected), description
        assert collatz_conjecture.steps(number) == Ok(expected)
    end
end

test "zero is an error"
    assert collatz_conjecture.steps(0) == Err("Only positive integers are allowed")
end

test "negative value is an error"
    assert collatz_conjecture.steps(-15) == Err("Only positive integers are allowed")
end
  • The sequence is Iter.iterate(number, next), cut at the first 1 with Iter.take_while(&(&1 != 1)) and counted. That states the problem directly; a tail-recursive counter was the other option. The cut is one comparison, so it is written as the capture &(&1 != 1) rather than as fn n -> n != 1.
  • A non-positive input returns Err with the canonical message, through an early return before the pipeline.
  • The four step counts are a subtests table; the two error cases are plain tests, since they assert a different shape.