CODEWITHSUNDEEP
javaloopsmathcollatz
bofredo
bofredo

Reputation: 2348

why does the loop die? ( Collatz conjecture )

i am trying some math-operations with java, that does test a number if its (un)even and alter it as long as it gets to 1.

I try to run my loop for 999999times, it seems to get stuck at around ~120000times. Well, it is not stopping with an Exception, it just feels like the compiler got stuck.

I'm not that good with Java, can someone explain me what is happening here?

public static void main(String[] args) {

    int n = 0;
    int highestNumber = 0;
    int highestCounter = 0;
    int counter = 0;
    for (int i = 2;i<1000000;i++) {

        if (i%10000==0) {
            System.out.println(i);
        }
        n = i;
        while (n!=1) {
            if (n%2==0) {   
                n = n/2;
            } else {    
                n=3*n+1;
            }
            counter++;
        }
        if (counter>highestCounter) {

            highestCounter = counter;
            highestNumber = i;
            System.out.println("HIGHEST "+highestNumber+" | counter = "+counter);   
        }
        counter = 0;
        n = 0;
    }
    System.out.println("final "+highestNumber);  
}

Upvotes: 5

Views: 601

Answers (5)

isnot2bad
isnot2bad

Reputation: 24454

You've got an overflow because 3 * n + 1 became larger than Integer.MAX_VALUE. So n gets negative and the while loop will never halt.

Use long instead of int for n!

If you want to check for the overflow instead:

while (n != 1) {
    if (n % 2 == 0) {
        n = n / 2;
    } else {
        if (n > (Integer.MAX_VALUE - 1) / 3) {
            throw new RuntimeException("overflow!");
        }
        n = 3 * n + 1;
    }
    counter++;
}

Addition for Java 8

Since Java 8, the Math class provides additional static methods for 'exact' arithmetics (addition, subtraction, multiplication, division) that throw an ArithmeticException in case of an overflow. Using these methods, the code can be simplified:

while (n != 1) {
    if (n % 2 == 0) {
        n = n / 2;
    } else {
        n = Math.addExact(Math.multiplyExact(3, n), 1);
    }
    counter++;
}

Upvotes: 10

Chris
Chris

Reputation: 959

Hmm, your code looks fine to me. You're solving a pretty typical problem

Is n an integer? If it's a short you might be overflowing it.

Other than that, an integer's max value is over 2 billion, so you shouldn't be hitting it. Just in case, try setting n to a long to see if that helps

Edit: Take for example, the number 77671 According to a blog I read (read: untested) the highest n for i = 77671 is 1,047,216,490

So I think n should be a long, now that I think more about it

Upvotes: 1

Gregory Klimov
Gregory Klimov

Reputation: 162

You simply running an infinite loop inside while block, add System.out.println(counter); after counter++ to see what's going on..

Upvotes: 0

Angelo Fuchs
Angelo Fuchs

Reputation: 9941

You have an overflow problem. Change the code like this and you see it:

    while (n!=1) {
        if(n < 0) throw new IllegalStateException("n should not become < 0" + n + "-" + counter);
        if(n > ((Integer.MAX_VALUE -1) / 3)) System.out.println("n too large. " + n);
        if (n%2==0) {   
            n = n/2;
        } else {    
            n=3*n+1;
        }
        counter++;
    }

if you make n to a long it works fine.

Upvotes: 4

luiso1979
luiso1979

Reputation: 918

This correction works:

public static void main(String []args){
    long highestCounter = -1;
    long highestNumber = -1;
    for (long i = 2;i<1000000;i++) {

        if (i%1000==0) {
            System.out.println(i);
        }
        long n = i;
        long counter = 0;
        while (n!=1) {
            if (n%2==0) {   
                n = n/2;
            } else {    
                n=3*n+1;
            }
            counter++;
        }
        if (counter>highestCounter) {

            highestCounter = counter;
            highestNumber = i;
            System.out.println("HIGHEST "+highestNumber+" | counter = "+counter);   
        }
        counter = 0;
        n = 0;
    }
    System.out.println("final "+highestNumber); 
}

Upvotes: 1

Related Questions