Project Euler - Problem 12

Welcome to week 12 of my Project Euler series.

Problem 12:

What is the value of the first triangle number to have over five hundred divisors?

Details:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Code:

// What is the value of the first triangle number to have over five hundred divisors?

class Problem0012

{

static void Main(string[] args)

{

int triangleNumber = 0;

int factors = 0;

int counter = 1;

while (factors <= 500)

{

factors = 0;

triangleNumber += counter;

for (int i = 1; i < (int)Math.Sqrt(triangleNumber); i++)

if (triangleNumber % i == 0)

factors+=2;

counter++;

}

Console.Write(triangleNumber);

Console.Read();

}

}

Solution:

This one is a pretty easy brute force solution.  Go through all the triangle numbers starting at one and see how many factors they have. If it is more than 500 then we have a winner.  Print and finished. The method needed to solve this one is given right in the details. It can be improved though. Because of the size of the numbers that we are working with here, I decided to apply one small bit of optimization just to spice things up.

This optimization that I applied was not a programmatic one, but rather a mathematical subtlety that I happened to remember.  If you add two to the factor count, you only have to go up to the square root. This works because it is not asking what the factors are, but rather just for the count. After the square root, you are just going to be going through the other side of the list. I went ahead and skipped that list in lieu of using this shortcut.

Until next time...

Enjoy!