Two days ago I had been looking at re-playing with Project Euler problems, after I solved a few of them last time (quite some time ago). I looked at the problem list, and decided to try solve the top-most unsolved problem I have: Problem 12. I managed to come up with a brute-force code that calculated the answer in about 403 ms on an Intel Core2 Duo T9600 @ 2.80GHz machine.

Understanding the problem

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, …

Given the example, I guess the mathematical function explanation of the triangle numbers would be something along this line: f(n) –> 1+2+3+…+n where n=1, 2, 3, …

We are then required to come up with something to find the first triangle number to have over 500 divisors. In clearer words, we are required to find the first triangle number to have 501 divisors, within one minute, complying to the Project Euler’s one-minute rule:

I’ve written my program but should it take days to get to the answer?

Absolutely not! Each problem has been designed according to a “one-minute rule”, which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

Spoiler alert: All that follows after this will be discussions of the solution I came up with for this problem.

Methods of solving

The methods I came up with are all purely brute-force, not making use of any proved mathematical methods, which if available, should be able to solve problems a lot more efficiently.

Brute-Force Method 1

The most inefficient way. The steps:

  1. Try to divide the current triangle number, n with the divisors: 1, …, n.
  2. Count the number of divisors that can be divided evenly.
  3. If the count reaches 501, stop, this is the triangle number we are looking for.
  4. If not, on to the next triangle number.

Brute-Force Method 2

Other than the number 1, the rest of the numbers (not just triangle numbers) will have at least two divisors: 1 and the number itself. And the biggest divisor for a number, besides the number itself, will not be more than the number itself divided by two. For example, the biggest divisor for the number 10, besides the number 10 itself, will not be more than 5.

The steps:

  1. Ignore the first triangle number: 1. Start directly with the second triangle number: 3 (result of 1+2).
  2. Start the count of divisors with 2, as all numbers other than 1 will have at least two divisors.
  3. Try to divide the current triangle number, n with the divisors: 2, 3, 4, …, n/2.
  4. Continue on with Step 2-4 of Brute-Force Method 1.

Brute-Force Method 3

Let’s think more cleverly:

  1. Every divisors are pairs. If a number divided by x results to y, the same number divided by y will result to x. E.g 10 / 5 = 2, 10 / 2 = 5. So for each divisor found, we can add 2 to the divisor count.
  2. There are also “twin-pairs divisors”. E.g 36 / 6 = 6. For each of these divisors found, we add 1 to the divisor count.

The steps:

  1. Start directly with the second triangle number: 3.
  2. Start the count of divisors with 2.
  3. Try to divide the current triangle number, n with the divisors: 2, 3, 4, … (while n / divisor > divisor). For each divisor that can be divided evenly, add 2 to the count of divisors.
  4. When n / divisor <= divisor, check to see if it is a “twin-pair divisor”. If it is, add 1 to the count of divisors.
  5. If the count reaches 501, stop, this is the triangle number we are looking for.
  6. If not, on to the next triangle number.

The basic C# code

I will be using the steps listed in Brute-Force Method 3 which is the best brute-force method I can come up with.

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Problem12
{
    class Program
    {
        static void Main()
        {
            long msecs = 0;
            int answer = 0;
            for (int i = 0; i < 10; i++) {
                Stopwatch stopwatch = Stopwatch.StartNew();
                answer = SolveUsingLinq(501);
                stopwatch.Stop();
                msecs += stopwatch.ElapsedMilliseconds;
            }
            Console.WriteLine("Answer: {0}", answer);
            Console.WriteLine("Elapsed: {0}", msecs / 10);
        }

        static int SolveUsingBasicMethod(int numberOfFactors)
        {
            foreach (int n in EnumSequenceOfTriangleNumbers()) {
                if (CountFactor(n) >= numberOfFactors) {
                    return n;
                }
            }

            // This code is unreachable. EnumSequenceOfTriangleNumbers will infinitely return the next triangle number, limited to Int32.MaxValue.
            return 0;
        }

        /// <summary>
        /// Returns a stream of triangle numbers, starting from the second triangle number: 3.
        /// </summary>
        static IEnumerable<int> EnumSequenceOfTriangleNumbers()
        {
            int i = 2;
            int n = 1;
            while (true) {
                n += i++;
                yield return n;
            }
        }

        /// <summary>
        /// Returns the number of factors / divisors for the given number using the steps outlined in Brute-Force Method 3.
        /// </summary>
        /// <param name="n">The number to have its factors counted.</param>
        /// <returns>The number of factors.</returns>
        static int CountFactor(int n)
        {
            int count = 2;
            int divisor = 2;
            int quotient = n / divisor;

            while (quotient > divisor) {
                if (n % divisor == 0) {
                    count += 2;
                }
                quotient = n / ++divisor;
            }

            if (quotient == divisor && n % divisor == 0) {
                count++;
            }

            return count;
        }
    }
}

This code took about 403 ms on an Intel Core2 Duo T9600 @ 2.80GHz to calculate the answer.

The LINQ version of the code

The actual reason I’m re-playing with the Project Euler’s problems is to learn new stuffs which I had no chance of learning at my workplace. And guess what: LINQ is still considered one of the things in my what’s new list. I had not much chance of doing anything with it as I’m still using Microsoft Visual Studio 2005 and .NET Framework 2.0 up till now, when Visual Studio 2008 had been around for quite some time and Visual Studio 2010 will be entering the market soon enough.

Enough rambles.

Back to the code, the LINQ version will be built on top of the basic code.

using System.Linq;

...

static int SolveUsingLinq(int numberOfFactors)
{
	var query = from n in EnumSequenceOfTriangleNumbers()
				where CountFactor(n) >= numberOfFactors
				select n;

	return query.First();
}

This code took about 404 ms. No noticeable time difference if compared against the basic code.

I will be looking into the even newer Parallel LINQ. The CountFactor method would be a good candidate to be executed in parallel i.e counting the factors of two triangle numbers at one time (two at a time since I am running the code on a dual core machine). I have some rough idea on coding manual threading for it, but let’s see how PLINQ can make it simpler. And perhaps I’ll try to do an F# version as well. ;)