Project Euler #14

I had so much fun doing #13 I thought I'd tackle #14 as well.

This problem wasn't too bad.  I started by defining some extension methods on long:

   1: static class Extensions
   2: {
   3:     public static long NextInSequence(this long number)
   4:     {
   5:         if (number % 2 == 0)
   6:         {
   7:             return number / 2;
   8:         }
   9:         else
  10:         {
  11:             return 3 * number + 1;
  12:         }
  13:     }
  14:  
  15:     public static IList<long> GenerateSequence(this long number)
  16:     {
  17:         List<long> seq = new List<long>();
  18:  
  19:         long next = 0;
  20:         do
  21:         {
  22:             next = number.NextInSequence();
  23:             seq.Add(next);
  24:             number = next;
  25:         } while (next != 1);
  26:  
  27:         return seq;
  28:     }
  29: }

While I don't necessarily need the full list of terms (GenerateSequence), I used the list in testing to make sure my sequence logic was correct.

Now, the only thing left to do was to find the longest sequence.  I used a LINQ query to order the list of sequence counts in descending order so the longest would be at the top:

   1: var range = Enumerable.Range(1, 1000000);
   2:  
   3: var biggest = (from n in range
   4:                let size = ((long)n).GenerateSequence().Count
   5:                orderby size descending
   6:                select new { Number = n, Length = size }).ToArray();
   7:  
   8: Console.WriteLine("{0} has a sequence of {1}", biggest[0].Number, biggest[0].Length);
Technorati Tags: ,,
Published Friday, December 19, 2008 9:19 PM by PSteele
Filed under: ,

Comments

No Comments