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")
endok counts the steps (4 cases)
ok zero is an error
ok negative value is an error
test result: ok. 6 passed, 0 failed
How it’s written
Section titled “How it’s written”- The sequence is
Iter.iterate(number, next), cut at the first 1 withIter.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 asfn n -> n != 1. - A non-positive input returns
Errwith the canonical message, through an earlyreturnbefore the pipeline. - The four step counts are a
subteststable; the two error cases are plain tests, since they assert a different shape.