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.

something about Java

Java's primitive data types 
How to convert ArrayList containing Integers to primitive int array?
What's difference between Math.pow(9, 18) and 9^18?
Reading integers from a file into an array
2D dynamic array using ArrayList 
When to use LinkedList<> over ArrayList<> or vice-versa? 
Java Hashtable versus HashMap. 
.toArray(new MyClass[0]) or .toArray(new MyClass[myList.size()])?
What are some Java memory management best practices? 
Publications and regular columns from Brain Goetz
Struct like object in Java.

Largest palindrome made from the product of two 3-digit numbers

This question is an entry level puzzle from Project Euler.

It is very interesting because it has far more pitfalls than it first appears to be. There are some helpful discussions to pick up the whole scenario of this puzzle: 1) and 2). Basically speaking, the first post listed the most straightforward thoughts, which is iterations two numbers both from 100 to 1000 and finding the maximum of the outcomes. While I wrote the algorithm, this is also the first idea came into mind while I added several optimizations on it.
1) Decrease one number 1 per step, and iterate the other one from 999 to 100.
2) Stop the step whenever it finds a palindrome and march to the next step by decrease the benchmark number by one.
3) Meanwhile, increase the lower bound of iterator from 100 to whenever it finds a palindrome. This will exponentially decrease the searching range. e.g. (A--benchmark number, B--iterator) if A*B==palindrome, the searching range for the next step would be [A-1, B]. Because if both numbers less than the previous finding, it must not be the LARGEST palindrome we would like to find.
4) The second stop criteria is the iterator equal or less than the lower bound mentioned in the last item.

The major pitfall that I did see quite a few people mentioned is alternative decrease two numbers from 999, which the result comes to be 834*836=698896. The difference for two numbers are obviously unnecessary to be less or equal to one.

The second reference provides the basic optimization from math point of view. All of the palindrome can be divided by 11, so...
P=100000x+10000y+1000z+100z+10y+x
P=100001x+10010y+1100z
P=11*(9091x+910y+100z)
Then, the question is simplified to find two 3-digit numbers, at least one of which should be divided by 11. Similarly as the previous method, if A can be divided by 11, decreasing B by one per time; and if A cannot divided by 11, decreasing B by 11 per time.

My solutions for the first 5 puzzles are here.
cheers,