Why is Collatz Conjecture Program Not Working for Large Integers in Java

Question

This is a program I made to simulate the Collatz Conjecture on Java:

import java.util.*;
public class Collatz {
public static void main(String args[]){
    Scanner raj= new Scanner(System.in);
    int n;
    int k=0;
    System.out.print("n? ");
    n = raj.nextInt();
    while(n > 1){
        if(n%2 ==1){
            n=3*n+1;
            System.out.println(n);
            k++;
        }
        if(n%2==0){
            n=n/2;
            System.out.println(n);
            k++;
        }

    }
    System.out.print("It took " + k + " iterations!");
}

}

When I put in n=6, I get

3 10 5 16 8 4 2 1 It took 8 iterations!

But when I put, say, n= 63728127, I get

191184382 95592191 286776574 143388287 430164862 215082431 645247294 322623647 967870942 483935471 1451806414 725903207 -2117257674 -1058628837 It took 14 iterations!

What went wrong? Why? How can I fix it? Thanks!

Answer 1

This is a classic case of integer overflow. Primitive ints have a limited range in Java. The solution is to always use something like BigInteger if you have to deal with large integers.

Incidentally, things would be so much easier if Java supported operator overloading like almost all other modern languages.

import java.util.*;
import java.math.BigInteger;


public class Collatz {
    public static void main(String args[]){
        Scanner raj= new Scanner(System.in);
        int k=0;
        System.out.print("n? ");

        BigInteger n = BigInteger.valueOf(raj.nextLong());

        while(n.compareTo(BigInteger.ONE) > 0){
            if(n.testBit(0)){
                n = n.multiply(BigInteger.valueOf(3));
                n = n.add(BigInteger.ONE);
                System.out.println(n);
                k++;
            }
            else {
                n = n.divide(BigInteger.valueOf(2));
                System.out.println(n);
                k++;
            }
        }
        System.out.print("It took " + k + " iterations!");
    }
}