Euler Problem 12

It’s been a long time since I have worked on any of the Euler problems.  I simply haven’t had time.  Well, it was time to spend a bit of time just exercising the math part of my mind, and solve another problem.

Problem 12 asks you to find the first triangle number that has more than 500 divisors.

Like my other C# solutions, it makes sense to decompose this problem into smaller sets. First, figure out how to generate the triangle numbers. Then, figure out the simplest way to determine how many divisors a number has.

Let’s start with the triangle numbers. The nth triangle number is the sum of all natural numbers less than or equal to N. You can think of them like the number of balls in a billiard rack with N rows:  1, (1+2), (1+2+3), (1+2+3+4), or, 1,3,6,10,15…

A little bit of math (or a quick search) will tell you that the Nth triangle number is [N * (N+1)]/2.

Now, all we need to do is compute the total number of divisors for each of these numbers. One simple answer is to take all number less than or equal to the triangle number. Any of those that divide into the triangle number is a divisor. But, that’s incredibly inefficient. Instead, you can stop at Sqrt(Number). That will give you exactly 1/2 the number of divisors. For example, if 128 is divisible by 2, you’ve found two divisors: 2, and 64. Therefore, this method tells me quickly how many divisors a number has:

   1: static int CountDivisors(int n)

   2: {

   3:     var divisors = from val in Enumerable.Range(1, (int)Math.Sqrt(n))

   4:                    where n % val == 0

   5:                    select val;

   6:  

   7:     return divisors.Count()*2;

   8: }

This query (written in two parts) finds the answer. Remember that one of the keys to LINQ is deferred execution. Only the triangle numbers up to and including the answer are generated.  The entire program runs in a few seconds:

   1: var triangleNumbers = from n in Enumerable.Range(1, 100000)

   2:                       let Value = (n * (n + 1)) / 2

   3:                       select new

   4:                       {

   5:                           Number = Value,

   6:                           NumDivisors = CountDivisors(Value)

   7:                       };

   8: var answer = (from vals in triangleNumbers

   9:              where vals.NumDivisors > 500

  10:                   select vals).First();

It feels good to stretch the math muscles again.