# Collatz Conjecture Meet of 2 Numbers

I need the most efficient way to calculate when the Collatz Conjecture of two numbers, a and b respectively, are the same. Here is my algorithm, which is too slow:

while(true) {
int a = sc.nextInt();
int b = sc.nextInt();

if(a == 0 && b == 0) {
break;
}

TreeMap<Integer, Integer> visited = new TreeMap<>();
visited.put(a, 0);

int A = a;
int Acount = 0;

while(A != 1) {
Acount++;

if(A % 2 == 0) {
A /= 2;
} else {
A = A * 3 + 1;
}

if(!visited.containsKey(A)) {
visited.put(A, Acount);
}
}

int B = b;
int Bcount = 0;

while(B != 1) {
if(visited.containsKey(B)) {
out.println(a + " needs " + visited.get(B) + " steps, " + b + " needs " + Bcount + " steps, they meet at " + B);
break;
}

if(B % 2 == 0) {
B /= 2;
} else {
B = B * 3 + 1;
}

Bcount++;
}

}


After looking around on Github, I found this, and it worked, although it's essentially the exact same thing.

Original problem

How do I fix my Java code to make it more efficient? I tried it literally at least four times.

• Please do not edit "solutions" into your questions. That would be good form on 90's forums, but here it only results in confusion. Thanks! Commented Aug 21, 2017 at 9:19
• (The alternatives to editing "solutions" into one's question include answering and posting another (cross-linked) question.) Commented Aug 21, 2017 at 9:22
• I see. Won't do that from now on :) Commented Aug 22, 2017 at 13:27

## 1 Answer

### Integer Overflow

I suspect that your problem has to do with integer overflow and not with your algorithm itself. If you don't guard against integer overflow, doing A = A * 3 + 1 could result in a negative value, and you may end up in an infinite loop where you never reach 1. Try changing your variables to long and resubmit.

By the way, to test for infinite loop cases, try the starting value 113383.

### Other suggestions

• You could use a HashMap instead of a TreeMap. A HashMap has $O(1)$ insert and lookup compared to $O(\log n)$ for a TreeMap. The difference for this program will be very small though.
• In the A loop, you shouldn't have to check if visited.containsKey(A) because the collatz sequence never repeats until you reach 1. You can just always add A to the map.
• If b is 1, your program never prints anything.
• Problem is TLE not WA. I tried a TreeMap still in vain :(. I have to do visited.containsKey(A) because visited maps the first occurrence of A, if I overwrite that value, I lose the index i which associates with number A such that it is at a minimum. It is essential to not overwrite it for the output (per problem statement). Commented Aug 20, 2017 at 6:12
• @ImagineDragons If you overflow you can get into an infinite loop, hence TLE. Did you even try it? As far as overwriting the first occurrence, the collatz sequence has no cycles except at 1 so you should never get a second occurrence except at 1.
– JS1
Commented Aug 20, 2017 at 6:25
• Trying right now, hopefully it works :). How can you prove it has no cycles where 1 < N <= 1 000 000 ? Commented Aug 20, 2017 at 6:31
• Hmm now I am getting WA for some reason, but it seems correct... Commented Aug 20, 2017 at 6:38
• @ImagineDragons See my latest edit. Your program doesn't work if b is 1. Also, did you remember to change your map to use Long instead of Integer?
– JS1
Commented Aug 20, 2017 at 6:44