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

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] = 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.

Recent Blog Activity

Blog Archive