Implement Iterator by hand: the Collatz sequence

Implement an iterator for the Collatz sequence, then use it to compute the sequence length and largest value for each starting number.

pub struct Collatz { pub n: u64 }

impl Iterator for Collatz { /* implement Item and next */ }

pub fn collatz_stats(starts: Vec<u64>) -> Vec<(u64, usize, u64)>

Sequence and result

A positive starting value is yielded first. After each value greater than one, the next value is n / 2 when n is even, or 3 * n + 1 when it is odd. Yield 1 once, then stop. A starting value of 0 yields nothing.

start 6: 6, 3, 10, 5, 16, 8, 4, 2, 1
start 1: 1
start 0: empty

Return one (start, length, maximum) tuple per input, preserving order and duplicates. The length counts yielded values, including the start and final 1. For start 6, return (6, 9, 16); for start 0, return (0, 0, 0). Empty input produces empty output.

Positive inputs for this exercise have trajectories that reach 1, whose values and 3 * n + 1 calculations fit in u64, and whose lengths fit in usize. This is a precondition of the exercise, not a claim that every positive integer is known to reach 1. No overflow or cycle policy is requested for inputs outside that domain.

Implement Iterator<Item = u64> for Collatz. In collatz_stats, use count() and max() on fresh instances of your iterator, rather than writing a second sequence loop. Output tests check the statistics; they cannot by themselves enforce the use of these methods.

The required pieces of Iterator

You supply the associated type Item and the method next(&mut self) -> Option<Self::Item>. The starter omits type Item = u64;, which produces E0046: a required trait item is missing.

Associated types let callers refer to the item type of a particular iterator implementation. Once Collatz implements Iterator, its item type is u64; callers do not choose a different item type for the same implementation.

Here is a complete, smaller iterator that counts down:

struct Countdown(u64);

impl Iterator for Countdown {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        if self.0 == 0 {
            return None;
        }
        let current = self.0;
        self.0 -= 1;
        Some(current)
    }
}

fn main() {
    let doubled: Vec<_> = Countdown(3).map(|n| n * 2).collect();
    assert_eq!(doubled, [6, 4, 2]);
    assert_eq!(Countdown(3).count(), 3);
    assert_eq!(Countdown(0).max(), None);
}

Provided methods such as map and count build on the iterator interface. Their bounds still matter: max requires ordered items, collect requires a suitable destination, and rev requires DoubleEndedIterator. Implementing next alone does not make a forward-only sequence reversible.

Represent the finished state

Use n == 0 as the finished state. For a positive state, remember the current value, update the state, then return Some(current). When the current value is 1, update the state to 0 so the next call returns None.

This ordering preserves the first value and includes the final 1. Updating first and yielding only the new state would skip the starting value.

For this exercise, further calls to next after exhaustion must return None while the state is left unchanged. General Iterator implementations are allowed to yield again after returning None; permanent exhaustion is an additional guarantee described by FusedIterator. The fuse() adapter can provide that behavior for an iterator without the guarantee.

Since n is public, explicitly assigning it a new positive start resets the state. That is different from an exhausted iterator resuming on its own.

Consume each traversal deliberately

count() consumes an iterator and returns a usize. max() consumes an iterator and returns an Option<u64>; use unwrap_or(0) for an empty sequence. Constructing two Collatz values gives each operation its own traversal.

The state is one integer, but traversing the sequence twice still performs work twice. A combined fold could compute both statistics in one traversal; this exercise asks for separate methods to practice consuming iterators. Collecting every value into a vector would also work mathematically, but would require storage proportional to the sequence length.

Use current.is_multiple_of(2) for the even branch. Clippy's manual_is_multiple_of lint flags the equivalent current % 2 == 0 pattern on the supported Rust toolchain. This is an API-style suggestion, not a guarantee that one spelling is faster.

After implementing the state machine, compare it with std::iter::successors, which builds an iterator from an initial optional value and a successor closure.