Problem #14
Difficulty: 5%
Longest Collatz Sequence
Solution Language: Java
The problem
The Collatz map halves an even number and sends an odd number n to 3n + 1. Find the starting value below one million whose sequence takes the most terms to reach 1.
My solution
Brute force. For every start from 3 to 999,999, chain follows the sequence all the way to 1 and counts the terms, and main keeps the start with the longest chain:
public static int chain(long n) {
int count = 1;
while(n != 1) {
if(n % 2 == 0)
n /= 2;
else
n = 3*n + 1;
count++;
}
return count;
}
The parameter is a long on purpose. Some starting values below one million climb past 2³¹ − 1 before coming back down, so an int would overflow and corrupt those chains. Starting at 3 skips 1 and 2, which can’t be the answer.
Chains below a million average on the order of a hundred steps, so the total is around 10⁸ simple operations.