Find the longest chain under 1M with Collatz Conjecture condition

It is the #14 problem in Project Euler.
In general, the Collatz conjecture has two main properties:
1. no infinite trajectory occurs;
2. no cycle occurs.

The basic algorithm is quite straightforward. It just follows the instruction of Collatz Conjecture, which are n = n/2 if n is even, and n = 3*n+1 if n is odd. To accelerate the calculation, I also implemented a hash map, which could be retrieve theoretically in constant time O(1), and use the iteration number as the key in this map and the overall steps towards 1 as the value of that key. Under this situation, whenever a new node is found, it will be added into the map, and continue the computation until it reaches some key which has already stored in the map. That is, the route is undetermined before the calculation, but every number only needs to calculate once.

The first problem I met is exactly the problem "Why am I getting an OutOfMemoryError trouble in Java?" described in the StackOverflow. When the program reaches 113383, all of the heap space will be consumed. As I looked up in the internet, all solutions point to how to increase the heap space for Java. While, as I narrowed down the bug to the innermost loop and print out every relevant variable, the bug finally turned out to be the overflow of integer data type. Just change it into long would solve this problem.

The second problem had the same symptom but with a much bigger number. When I print out every variable this time, nothing seemed wrong. But if we check the memory usage in run-time, all of the memory had been consumed by the hash map as some number will have extremely long chain towards 1, part of which are far beyond the range of 1000000. The scale is over 1.5 million items in hash map to achieve 725343. The solution is that the program only record number under 1 million, which are within the searching range and also most likely to be hit.


Solution discussions: [1] (discussion in StackOverflow), [2] (in JavaScript), [3] (optimization), [4] (in C++), [5] (in Python). By the way, here is the discussion about looking up memory usage during run time in Java--it helps me find the 2nd bug. Finally, my solution is in one of my Github repositories.