Use of integers and doubles give different answers when they shouldn't

Question

I'm solving a Project Euler Problem 14 using java. I am NOT asking for help solving the problem. I have already solved it, but I ran into something I can't figure out.

The problem is like this:

The following iterative sequence is defined for the set of positive integers:

n = n/2, if n is even
n = 3n + 1, if n is odd

Using the rule above and starting with 13, we generate the following sequence:

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1. Here, the length of the chain is 10 numbers.

Find the starting number below 1,000,000 that produces the longest chain.

So I wrote this code:

public class Euler014 {
    public static void main(String[] args){
        int maxChainCount = 0;
        int answer = 0;
        int n;
        int chainCount = 1;

        for(int i = 0; i < 1000000; i++){
            n = i;
            while(n > 1){
                if(n%2 == 0){       //check if even
                    n /= 2;
                }else{              //else: odd
                    n = 3*n + 1;
                }
                chainCount++;
            }
            if(chainCount > maxChainCount){ //check if it's the longest chain so far
                maxChainCount = chainCount;
                answer = i;
            }
            chainCount = 1;
        }       
        System.out.println("\n\nLongest chain: i = " + answer);     
    }
}

This gives me the answer 910107, which is wrong.

HOWEVER, if i change the type of my n variable to double n it runs and gives me the answer 837799, which is right!

This really confuses me, as I can't see what the difference would be at all. I understand that if we use int and do divisions we can end up rounding numbers when we don't intend to. But in this case, we always check to see if the n is divisble by 2, BEFORE dividing by 2. So I thought that it would be totally safe to use integers. What am I not seeing?

This is the code in its entirety, copy, paste and run it if you'd like to see for yourself. It runs in a couple of seconds despite much iteration. =)

Answer 1

Your problem is overflow. If you change int n to long n, you'll get the right answer.

Remember: The numbers in the sequence can be really big. So big they overflow int's range. But not (in this case) double's, or long's.

At one point in the chain, n is 827,370,449 and you follow the 3n + 1 branch. That value wants to be 2,482,111,348, but it overflows the capacity of int (which is 2,147,483,647 in the positive realm) and takes you to -1,812,855,948. And things go south from there. :-)

So your theory that you'd be fine with integer (I should say integral) numbers is correct. But they have to have the capacity for the task.