CODEWITHSUNDEEP
javainfinite-loopinteger-overflow
AleArk
AleArk

Reputation: 417

Sudden infinite loop above certain input argument?

While learning Java I'm redoing some of the Project Euler problems. This is about Problem 14 - Longest Collatz sequence: https://projecteuler.net/problem=14

My programm runs just fine for a lower CEILING like 1000, but when executed like posted it loops infinitely, I think? What goes wrong here?

public class Test {
    public static void main(String[] args) {
        int tempMax = 0;
        final int CEILING = 1_000_000;

        for (int j = 1; j < CEILING; ++j) {
            tempMax = Math.max(tempMax, collatzLength(j));
        }
        System.out.println(tempMax);
    }

    static int collatzLength(int n) { //computes length of collatz-sequence starting with n
            int temp = n;

            for (int length = 1; ; ++length) {
                if (temp == 1) 
                    return length;
                else if (temp % 2 == 0)
                    temp /= 2;
                else
                    temp = temp * 3 + 1;
            }
    }
}

Calling System.out.println(collatzLength(1000000)); seperately works just fine so I think we can rule an error here out.

Upvotes: 2

Views: 77

Answers (1)

kai
kai

Reputation: 6887

You should use long instead of int. The int overflows while doing your calculations in collatzLength and that causes the infinite loop. From the problem description:

NOTE: Once the chain starts the terms are allowed to go above one million.

The number causing the problem: 113383

The long version gives a result, which is still incorrect because you are printing the length of the longest chain, but you need the number which produces the longest chain.

public static void main(String[] args)
{
    int tempMax = 0;
    final int CEILING = 1_000_000;

    for (int j = 1; j < CEILING; ++j)
    {
        tempMax = Math.max(tempMax, collatzLength(j));
    }
    System.out.println(tempMax);
}

static int collatzLength(long n)
{
    long temp = n;

    for (int length = 1;; ++length)
    {
        if (temp == 1)
            return length;
        else if (temp % 2 == 0)
            temp /= 2;
        else
            temp = temp * 3 + 1;
    }
}

Upvotes: 5

Related Questions