Which starting number, under one million, produces the longest chain : Collatz Problem


/*
 * The following iterative sequence is defined for the 
 * set of positive integers:
 * 
 * n ->  n/2 (n is even)
 * n -> 3n + 1 (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
 * 
 * It can be seen that this sequence (starting at 13 and finishing at 1) 
 * contains 10 terms. Although it has not been proved yet (Collatz Problem), 
 * it is thought that all starting numbers finish at 1.
 * 
 * Which starting number, under one million, produces the longest chain?
 * 
 * NOTE: Once the chain starts the terms are allowed to go above one million.
 */


/**
 *
 * @author Umang Bhatt
 * bhatt.umang7@gmail.com
 */
public class Problem_14
{

    /**
     * contains logic for next no depending on the number
     * @param no is the number from which next no is to be calculated
     * @return the next number based on odd even logic
     */
    public static long getNextNo(long no)
    {
        long ans;
        if (no % 2 == 0)
        {
            ans = (no / 2);
        } 
        else
        {
            ans = ((3 * no) + 1);
        }
        return ans;
    }

    /**
     * gets no of items in chain for given no (chain ends at 1)
     * @param no is the number for which the no of items in chain is to be found out
     * @return no of items in chain
     */
    public static int getChainItemCount(long no)
    {
        long ans = no;
        int count = 1;
        while (ans != 1)
        {
            ans = getNextNo(ans);
            count++;
        }
        return count;
    }

    public static void main(String args[])
    {
        long maxCount = 0;
        long maxNoProducesMaxCount = 0;
        for (long i = 1; i <= 10_00_000; i++)
        {
            int ans = getChainItemCount(i);
            if (ans > maxCount)
            {
                maxCount = ans;
                maxNoProducesMaxCount = i;
            }
        }
        System.out.print(" maxCount " + maxCount + "\nNO : " + maxNoProducesMaxCount);
    }
}