### Challenge: Longest Collatz Sequence

Posted on: July 15, 2016 12:30:43 AM

This challenge wants you to find the longest collatz series between 1 and 1000000. A collatz series is defined by:
n → n/2 (n is even)
n → 3n + 1 (n is odd)

Example: n = 13
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
Program.cs
```using System;

namespace ProjectEuler_14
{
internal class Program
{
private static void Main(string[] args)
{
const int MaxNum = 1000000;
int highestCollatzSeriesCount = 0;
int numWithHighestSeries = 0;
// a cache can be used because all the series number eventually will get to
// a series that's already been calculated; therefore, this will save a lot
// of calculation time
int[] cache = new int[MaxNum + 1];

// 1 has a collatz series count of 1
cache = 1;

// start the loop at 2 since, in theory, all numbers end with 1
for (int i = 2; i < MaxNum; i++)
{
int count = 0;
// use a long because int will likely overflow at higher numbers
long collatz = i;
do
{
//n → n/2 (n is even)
//n → 3n + 1(n is odd)
if (collatz % 2 == 0)
{
collatz /= 2;
}
else
{
collatz = (collatz * 3) + 1;
}

count++;
// we can break the loop if collatz=1 or collatz > i
// because if it is less than i, it's been cached
} while (collatz != 1 && collatz > i);

// add the cached number to the total count
count += cache[collatz];

// cache the value
cache[i] = count;

if (count > highestCollatzSeriesCount)
{
highestCollatzSeriesCount = count;
numWithHighestSeries = i;
}
}

// print out the result
Console.WriteLine("Number with highest collatz series below {0}: {1} with {2} in series.", MaxNum, numWithHighestSeries, cache[numWithHighestSeries]);
}
}
}
```

Since memory wasn't a huge concern, I decided to cache the collatz sequence counts for every calculation so that I am not wasting CPU cycles repeating calculations. This ended up making the total run time to be less than 1 second whereas without caching took roughly 30 seconds.

No comments yet, be the first to leave one.

Recent Blog Activity
Blog Archive