I guess I was thinking about indexing the visited numbers from a graph-traversal-algorithm-interview perspective instead of a CS theory one. We can actually do

I guess I was thinking about indexing the visited numbers from a graph-traversal-algorithm-interview perspective instead of a CS theory one. We can actually do it in O(1) space complexity in exchange for higher time complexity. For i in range 1..n, compute n_i, the ith number in the hailstone iteration, and then continue the hailstone iteration n_(i+1)..n_max to see if n_i is equal to any of them. This takes us to quadratic time complexity, O(n * n_max), or constant complexity depending on how you look at it, but it only requires storing a single n_i at a time for cycle detection. But then again, if you actually loop for n_max iterations without halting by reaching 1 or crashing, then you had to reuse a number somewhere, so the explicit cycle detection isn’t really important.