Problem 14: Longest Collatz sequence

Problem:

Please find the problem here.

Solution:

Given the sequence is so random, I am not hoping to be able to count it without going through it. Going through all sequences, however, is going to take long time. Therefore, we need to find a trick to improve it.

The key idea is after going through 1 chain, we will know the length of all elements in the chain. In the example, we know 13 has a length of 10, but we also know 40 has a length of 9, and so on.

Suppose we have another sequence that have k → 40 → ... , we know k is going to have a length 10. Optimization like that save a lot of time because repeated checking of the same sequences is eliminated, and in practice the problem involve many repeated sequences.

This trick is generally called memoization (NOTE: Don't be confused this work with memorization, they spell differently). The code is pretty simple.

namespace Euler
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    internal static partial class Program
    {
        public static void Problem014()
        {
            var lengths = new Dictionary<long, long>();
            for (long i = 1; i <= 1000000; i++)
            {
                Length(i, lengths);
            }
            var lengthSorted = lengths.ToList();
            lengthSorted.Sort((x, y) => (x.Value < y.Value) ? 1 : ((x.Value == y.Value) ? 0 : -1));


            Console.WriteLine(lengthSorted[0].Key);
        }

        private static long Length(long x, Dictionary<long, long> lengths)
        {
            if (x == 1)
            {
                return 1;
            }
            else
            {
                long result;
                if (lengths.TryGetValue(x, out result))
                {
                    return result;
                }
                else
                {
                    long next = x % 2 == 0 ? x / 2 : (3 * x + 1);
                    result = 1 + Length(next, lengths);
                    lengths.Add(x, result);
                    return result;
                }
            }
        }
    }
}

Answer: 837799