3 ms·

We have actually done something like that up to the 32bit n_max for sure (but maybe even 64bit?), without any number that would contradict the conjecture. But

• odyssey7 3y ago
  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.