Cat Tran Cat Tran - 7 months ago 23
Java Question

Searching longest chain in Collatz sequence in Java, loop not terminating

I want to apply the Collatz Sequence and apply it to all numbers from 1 to 10^6, and return the number with the largest chain needed to reach 1. However, I have the problem that my loops dont seem to terminate in Eclipse and I can't figure out why, I can't even get all my prints shown in the console despite wanting it out every step.

The collatz sequence is is computed by the following rules:


  • if n is odd, the next number is n/2

  • if n is even, the next number is 3n + 1



This is what I have so far:

public static long collatz() {

long res = 0;
long n = 1;
long count = 0;
long largestCount = 0;
long t = 0;

for (long k = 1; k <= 20; k++) {

n = k;

while (n != 1) {

if ((n % 2) == 0) {
n = n / 2;
count = count + 1;
}

else {
n = (3 * n) + 1;
count = count + 1;

}

if (count > largestCount) {
largestCount = count;
res = k;
}
}
}

System.out.println(res);
return res;

}

Answer

Your code should run properly. It is not working code though. You are checking the condition to see if the current count is greater than the present largest count inside the while loop, which does not really make sense, since you need to get the length of the collatz sequence and then compare it to the current maximum. Other than that, your code is good. :)

This is something I had written up, if you are interested.

final int number = 1000000;

long sequenceLength = 0;
long startingNumber = 0;
long sequence;

for (int i = 2; i <= number; i++) {
    int length = 1;
    sequence = i;
    while (sequence != 1) {
        if ((sequence % 2) == 0) {
            sequence = sequence / 2;
        } else {
            sequence = sequence * 3 + 1;
        }
        length++;
    }

    //Check if sequence is the best solution
    if (length > sequenceLength) {
        sequenceLength = length;
        startingNumber = i;
    }
}
System.out.println(startingNumber);