Project Euler Problem 12

This post tackles Problem 12 in the Project Euler Series

If you've ever played pool then you'll already be acquainted with the subject of today's problem: if not, meet the triangle numbers. Imagine you have a triangle of pool balls arranged on a green baize table. Now take a big black marker pen and start counting from the tip of the triangle. At the end of every row of balls write down on the table the total number of balls so far. The sequence of numbers you've written down are the first few triangle numbers; the black eye and the permanent ban from the pool club are because you weren't paying attention: I said imagine! Now you've learned the hard way, you should be able to see how to extend the sequence to find further triangle numbers. As you have just discovered, the first few numbers are 1, 3, 6, 10, 15, 21, and so on.

Today's problem requires us to calculate the number of divisors of each triangle number, and then report the first one to have over 500. Let's get started.

The first job is to generate the sequence of triangle numbers in code. This is bread-and-butter to us now, but I'll throw in a bit of salami to keep things interesting.

If we wanted to generate any particular triangle number - say the nth- we could just use the Sum() function on the sequence 1.To(n) - or, more abstractly, use the Aggregate function to add each item in the sequence to the running total. But we need to generate the whole infinite sequence of triangle numbers - because we don't know before hand how many we'll need.

To help with this, I've created the LazilyAggregate extension method. This acts on a sequence, and returns a sequence of partial aggregates. You use it like this:

var triangleNumbers = 2.To(int.MaxValue)
                      .LazilyAggregate(
                        1,
                        (item, accumulatedValue) => accumulatedValue + item);

The first argument is the seed value - this will be the first item in returned sequence. The second argument is a lambda function which takes two parameters: the first being the next item in the sequence to aggregate, the second, the aggregated value so far. The value returned by the lambda is pushed to the output sequence, and also fed through to the next call of the lambda.

The next step is to enumerate all the divisors of each triangle number. Unlike previous problems, we don't want just the prime factors, but every single number that divides into our candidate.

We can speed up the generation of this divisor list by remembering that divisors always come in pairs: one factor will be less than Sqrt(n), the other will be bigger (unless of course n is a square number!). In the code below, the inner from expression is generating a sequence of pairs of divisors, my Concat() extension method is unpacking the pairs to create one long sequence of divisors which is then counted. The outer from clause will pick out only the triangle numbers with more than 500 divisors - and we take just the first from that sequence. A nd we're done.

The complete code is shown below, and can be downloaded from the Project Euler page on the MSDN Code Gallery.

[EulerProblem(12, Title="What is the value of the first triangle number to have over five hundred divisors?")]
public class Problem12
{
    public void Solve()
    {
        var triangleNumbers = 2.To(int.MaxValue)
                              .LazilyAggregate(
                                1,
                                (item, accumulatedValue) => accumulatedValue + item);

        var result = (
                     from n in triangleNumbers
                     where
                            (from factor in 1.To((int)Math.Sqrt(n))
                            where n.IsDivisibleBy(factor)
                            select new int[] { factor, n / factor } )
                            .Concat()
                            .Count() > 500
                     select n
                     )
                     .First();

        result.DisplayAndPause();
    }
}

public static class Extensions
{
    public static IEnumerable<TAccumulate> LazilyAggregate<T, TAccumulate>(this IEnumerable<T> sequence, TAccumulate seed, Func<T, TAccumulate, TAccumulate> aggregator)
    {
        var accumulatedValue = seed;
        yield return seed;

        foreach (var item in sequence)
        {
            accumulatedValue = aggregator(item, accumulatedValue);
            yield return accumulatedValue;
        }
    }

    public static bool IsDivisibleBy(this long number, long factor)
    {
        return number % factor == 0;
    }

    public static IEnumerable<int> To(this int first, int last)
    {
        if (first == last)
        {
            yield return first;
        }
        else if (first < last)
        {
            for (var l = first; l <= last; l++)
            {
                yield return l;
            }
        }
        else
        {
            for (var l = first; l >= last; l--)
            {
                yield return l;
            }
        }
    }

    public static void DisplayAndPause(this object result)
    {
        Console.WriteLine(result);
        Console.ReadLine();
    }

    public static IEnumerable<T> Concat<T>(this IEnumerable<IEnumerable<T>> sequences)
    {
        return sequences.SelectMany(sequence => sequence);
    }

    public static IEnumerable<T> Concat<T>(this IEnumerable<T[]> sequences)
    {
        return Concat(sequences.Cast<IEnumerable<T>>());
    }
}