Problem: The Collatz Sequence

The iterators we have written so far traversed the elements of a set or a list. But an iterator does not need a data structure to traverse. It can compute each value when it is asked for one, without storing any of them. To see that, write an iterator for the Collatz sequence.

The sequence starts at a positive integer n and follows two rules until it reaches 1:

• if the current number is even, divide it by 2;
• if the current number is odd, multiply it by 3 and add 1.

Starting from 3, it goes:

3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Write a class MathSequence that implements Iterable<Integer>, so that an enhanced for loop can go through the sequence:

MathSequence sequence = new MathSequence(3);
for (int value : sequence) {
  System.out.println(value);  // 3, 10, 5, 16, 8, 4, 2, 1
}

Both hasNext() and next() must run in $O(1)$ time, and the iterator must use $O(1)$ space. That means it may not precompute the whole sequence or store it. next() throws NoSuchElementException when it is called after 1 has been returned, and the constructor rejects n <= 0.