Java, out of memory, inefficient function

Question

I'm writing a program that is supposed to create chains of numbers and see witch one is the longest. The problem is that I run out of memory and I have no idea what eats all of the memory. Does anyone know were the problem is?

public static void main(String[] args) {

    ArrayList<Integer> longestchain;
    ArrayList<Integer> chain = new ArrayList<Integer>();
    int size = 0;
    int longestsize = 0;
    int start;
    int number = 0;

        for(int i = 3; i < 1000000; i++)
        {
            start = i;
            chain.clear();
            chain.add(start);
            size = 1;
            while(true)
            {
                if(start == 1)
                {
                    break;
                }
                if(iseven(start))
                {
                    start = start / 2;
                }
                else
                {
                    start = start*3 + 1;
                }

                chain.add(start);
                size++;

            }

            if(size > longestsize)
            {
                longestsize = size;
                longestchain = chain;
                number = i;

            }
            //System.out.println(i);

        }
        System.out.println(number + ". " + longestsize);

}

public static boolean iseven(int n)
{
    return (n % 2 == 0);
}

Answer 1

The problem is that when i=113383 you're running into an integer overflow. This results in an infinite loop that keeps adding to chain until you run out of heap space. Change chain and longestchain to ArrayList<Long>, start to long and iseven() to take long, and you'll solve that particular problem.

Another problem is that longestchain = chain assigns the reference, whereas you need to copy the contents. Otherwise the next iteration will wipe longestchain.

Answer 2

Don't know why are you running out of memory, but I noticed a bug in your code - longestchain and chain point to the same object, so when you clear chain, you also clear longestchain. You can fix it by creating a new array with contents of chain instead of an assignment.

Answer 3

This will probably not be the solution, but a hint:

The default array size for an ArrayList is 10. Initialize your ArrayLists to a value closer to what you are expecting, or many array creations happen under the hood:

// e.g.
ArrayList<Integer> chain = new ArrayList<Integer>(50000);