A fun experiment with the Collatz Conjecture

I’ve been working through Project Euler in C# recently and was thrilled when I saw a challenge revolving around the Collatz Conjecture.

For the uninitiated, it goes like this:

Consider a number (x). If x is even, halve it. If it’s odd, triple it and add 1 to it.

Repeat this until x = 1.

Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

This simple algorithm creates long chains of numbers that can be arranged into trees as shown below:

Now for the challenge:

Which starting number, under one million, produces the longest chain?

This question presented a great programming challenge perfectly suited for a language like C#.

Let’s dive in!

This project is going to involve a lot of data-reuse.

Consider the following:

Collatz(6): 6->3->10->5->16->8->4->2->1

Collatz(5):5->16->8->4->2->1

These sequences, presumably like all others end in 16, 8, 4, 2, 1 — and 5 always leads to that sequence. Therefore, for each new number we only need to calculate the sequence until we reach a number we have already calculated.

Let’s code it.

The question calls for us to return the number which has the longest chain so we’ll need a dictionary to store the number and the length of its chain:

   //We're using a dictionary to store the KV pairs for the number and
   //collatz length because it is conceptually the same
   //as a hashtable and as such is much faster than an array
Dictionary<long, long> CollatzLengths = new Dictionary<long, long>();

We could also use a jagged array here, but dictionary indexing is much faster, so a Dictionary is better.

Next we’ll need a function to actually calculate the Collatz Chain for a given number:

static void Collatz(int number, Dictionary<long, long> CollatzLengths)
  {
   int initialNumber = number;
   long workingNumber = number;
   int steps = 0;
   while (workingNumber != 1)
   {
    //increase efficiency by using the results from previous
    //collatz calculations
    if (CollatzLengths.ContainsKey(workingNumber))
    {
     CollatzLengths.Add(initialNumber, steps + CollatzLengths[workingNumber]);
     return;
    }
    //if even, divide by 2
    if (workingNumber % 2 == 0)
    {
     workingNumber /= 2;
    }
    //if odd, *=3 and +1
    else workingNumber = (workingNumber * 3) + 1;

    steps += 1;
   }
   //if we reach 1 without touching another previous answer, add the
   //answer to the dictionary
   CollatzLengths.Add(initialNumber, steps);
   return;

This function takes the number whose chain we want to find and the dictionary of all numbers and their chain lengths. If we reach a number we’ve already calculated the Collatz Chain length for, we just add the current length to that number’s length to get the final length of our working number.

Now we need a loop to send in the numbers from 1 to 999,999 and report on the longest chain:

   // find the largest value by key.
   long maxValue = 0;
   int maxKey = 0;
   foreach (int key in CollatzLengths.Keys)
   {
    if (CollatzLengths[key] >= maxValue)
    {
     maxKey = key;
     maxValue = CollatzLengths[key];
    }
   }
   Console.WriteLine($"The starting number {maxKey} produces the longest chain at length {maxValue}");

Put it all together and we now know that the longest Collatz Chain produced by a number less than 1,000,000 is:

524, from the number 837799.