-5
\$\begingroup\$

Inspired by Project Euler 14:

Longest Collatz Sequence

"Which starting number, under one million, produces the longest Collatz Sequence chain?"

I wrote the following Java code:

public static void main (String[] args) {
    int max = 0;
    int num = 0;
    int result = 0;
    List<Integer> num_array = new ArrayList<Integer>();

    for (int i = 2; i < 100000; i++) {
        num = i;
        num_array.clear();
        while (num != 1) {
            if (num % 2 == 0) {
                num = num / 2;
            } else {
                num = 3 * num + 1;
            }
            num_array.add(num);
        }
        int len = num_array.size();
        if (len > max) {
            max = len;
            result = i;
        }
    }

    System.out.printf("%d, %d", result, max);
}

When bounded to 100000 it works fine, and returns the expected result. Unfortunately, when trying to use the requirement of the Project Euler problem (1000000) as the upper bound, it gives me an 'OutOfMemoryError' that the heap is full.

I was wondering, is there any way I can optimize this code to work with the Project Euler 14 upper bound requirement?

\$\endgroup\$
  • \$\begingroup\$ Welcome to CodeReview, in order to review your code it needs to be fully functioning. \$\endgroup\$ – Denis Dec 26 '16 at 19:58
  • \$\begingroup\$ @denis If it is working for smaller inputs but not for large ones then it is an optimization problem which is on-topic for Code Review. \$\endgroup\$ – Simon Forsberg Dec 26 '16 at 20:01
  • 3
    \$\begingroup\$ That's why I said fully apparently OP is looking for advice on how to make the code work for larger inputs, rather than review of the code in it's current state, correct me if I am wrong @SimonForsberg . \$\endgroup\$ – Denis Dec 26 '16 at 20:03
  • \$\begingroup\$ @denis So you're complaining about the phrase "How can I resolve this?" what if it instead was "How can I optimize my existing code for this?". \$\endgroup\$ – Simon Forsberg Dec 26 '16 at 20:13
  • \$\begingroup\$ In that case the question is valid or on-topic if you want to, but that's not it. Those are 2 completely different things aren't they ? \$\endgroup\$ – Denis Dec 26 '16 at 20:16
3
\$\begingroup\$

There is usually a way to fix this.

As stated earlier your current algorithm is inefficient. First: you keep this list but you don't use it for anything other than keeping a count of the number of elements to compare with the max. You could easily rewrite this algorithm to use a simple chainSize integer instead.

public static void main (String[] args) {
    int max = 0;
    int num = 0;
    int result = 0;
    int chainSize = 0;

    for (int i = 2; i < 100000; i++) {
        chainSize = 0;
        num = i;
        while (num != 1) {
            if (num % 2 == 0) {
                num = num / 2;
            } else {
                num = 3 * num + 1;
            }
            chainSize++;
        }
        if (chainSize > max) {
            max = chainSize;
            result = i;
        }
    }

    System.out.printf("%d, %d", result, max);
}

And now your 'OutOfMemory' error should be fixed. This is the first suggestion that Simon stated.

But, if you test it, you might find that for 1000000 it doesn't solve your 'OutOfMemory' issue. Why? Because we're using the wrong data-type. Specifically, for value 113383 we end up going above the maximum value of a signed integer. You need to be using the long data type for your iteration to fix that.

I wrote a version which tells me when it happens, and got the following:

Value from chain 113383 at length 120 above integer max: 2482111348

So at 120 calculations the chain from initial value 113383 exceeds the integer maximum. In an Int32 type this will become a negative number, which enters an infinite loop:

Value from chain 113383 at length 120 is negative: -1812855948
Value from chain 113383 at length 121 is negative: -906427974
Value from chain 113383 at length 122 is negative: -453213987
Value from chain 113383 at length 123 is negative: -1359641960
Value from chain 113383 at length 124 is negative: -679820980

Then we get to:

Value from chain 113383 at length 217 is negative: -68
Value from chain 113383 at length 218 is negative: -34
Value from chain 113383 at length 219 is negative: -17
Value from chain 113383 at length 220 is negative: -50
Value from chain 113383 at length 221 is negative: -25
Value from chain 113383 at length 222 is negative: -74
Value from chain 113383 at length 223 is negative: -37
Value from chain 113383 at length 224 is negative: -110
Value from chain 113383 at length 225 is negative: -55
Value from chain 113383 at length 226 is negative: -164
Value from chain 113383 at length 227 is negative: -82
Value from chain 113383 at length 228 is negative: -41
Value from chain 113383 at length 229 is negative: -122
Value from chain 113383 at length 230 is negative: -61
Value from chain 113383 at length 231 is negative: -182
Value from chain 113383 at length 232 is negative: -91
Value from chain 113383 at length 233 is negative: -272
Value from chain 113383 at length 234 is negative: -136
Value from chain 113383 at length 235 is negative: -68

As you can see, we hit -68 twice, which means it's in an infinite loop.

Just for fun:

Largest number in any chain: 56991483520

\$\endgroup\$
2
\$\begingroup\$

Your current situation:

You are storing all the visited numbers in a list and then querying only the size of the list. Instead of doing this you can instead have a single variable that keeps track of the number of visited numbers. You don't need a list.


Optimal solution:

Remember all the visited numbers and for each number store the number of visited numbers. For example, for the number 3 the next number is 10. So calculate the Collatz sequence for the number 10 and then add one. Then when your outer loop actually reaches the number 10, you can use the number you calculated before as you already know the Collatz Sequence for the number 10.

Hint: There is a good data structure you could use for this

\$\endgroup\$
  • \$\begingroup\$ Your suggestion is optimal for speed, but not for memory. As usual, you can save memory by sacrificing speed: calculate the result for each number individually and store just the biggest so far. \$\endgroup\$ – rossum Dec 26 '16 at 20:25
  • \$\begingroup\$ @rossum In this case, I'd prefer to optimize for speed. It's impossible to optimize for both. But feel free to post an answer suggesting a memory optimization. \$\endgroup\$ – Simon Forsberg Dec 26 '16 at 20:28
  • \$\begingroup\$ @SimonForsberg You could optimize for both by limiting how many sequence results you store. If you limit it to storing 10000 sequence results, then for those 10,000 sequence results you no longer need to calculate everything. \$\endgroup\$ – Der Kommissar Dec 26 '16 at 21:17
1
\$\begingroup\$

As Simon suggested, here is a memory optimised solution. I keep track of the current best solution using only two variables: bestLength and bestStart:

public static void main(String[] args) {

    long timeStart = System.nanoTime();

    int bestLength = 1;
    int bestStart = 1;

    for (int i = 2; i < 1000000; ++i) {

       int current = chainLength(i);
       if (current >= bestLength) {
           bestLength = current;
           bestStart = i;

           // Optional to show progress.
           // System.out.println("New best at " + i + " = " + current);
       }

    }

    System.out.println("Best length = " + bestLength + " starting at " + bestStart);

    long timeTaken = (System.nanoTime() - timeStart) / 1000000L;
    System.out.println("Time taken: " + timeTaken + " ms.");

    System.out.println("Finished.");

} // end main()


// Needs a long otherwise get integer overflow.
static int chainLength(long num) {

    int count = 1;

    while (num > 1L) {
        num = (num % 2L == 0L) ? num / 2L : 3L * num + 1L;
        ++count;
    }

    return count;

} // end chainLength()

This runs in about 500ms on my machine and uses a lot less memory than an array. I always run a timer on my Project Euler solutions; feel free to remove if you want to.

\$\endgroup\$
  • \$\begingroup\$ Side note: It is recommended to use System.nanoTime for measuring how long an operation took. System.currentTimeMillis can be misleading if the system time would change. \$\endgroup\$ – Simon Forsberg Dec 26 '16 at 21:28
  • \$\begingroup\$ @Simon. Thanks for that. I've been using a standard framework for Project Euler solutions for a long time now. I'll update it. \$\endgroup\$ – rossum Dec 26 '16 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.