Problem 12: Highly divisible triangular number

Problem:

Please find the problem here.

Solution

It is easy to generate triangle number, what is not easy is to count the number of divisors. Here we should say something about the divisor function. Simply put, the divisor function, denoted by $ \sigma(n) $ of a positive integer $ n $ counts the number of positive factors (including 1 and n) a number has. For example, we have $ \sigma(3) = 2 $ because 1 and 3 are the only factors for 3.

A key property of the divisor function is that it is multiplicative. That is to say, if GCD(p, q) = 1, then $ \sigma(p \times q) = \sigma(p) \times \sigma(q) $. This can be proved by creating a bijection between a factor of $ p \times q $ and the pair of factors of $ p $ and $ q $.

The divisor function value of a prime power is particularly easy. Suppose $ p $ is prime, then $ \sigma(p^n) = n + 1$ because the only factors are 1, $ p $, $ p^2 $, ..., $ p^n $.

Now we know how to compute the divisor function by completely factorize the number into prime powers, and leverage the multiplicative property.

Last but not least, it is easy to see the n^th triangular number is simply $ \frac{n(n+1)}{2} $. We will simply compute a factorization of it by brute force. The following is the code.

namespace Euler
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    internal static partial class Program
    {
        public static void Problem012()
        {
            long n = 1;
            while (true)
            {
                long t = n * (n + 1) / 2;
                int numberOfDivisors = BruteForceFactor(t).Select(p => p.Item2 + 1).Aggregate((x, y) => x * y);
                if (numberOfDivisors > 500)
                {
                    Console.WriteLine(t);
                    break;
                }
                n++;
            }
        }

        // Brute-force factoring 
        private static IEnumerable<Tuple<int, int>> BruteForceFactor(long n)
        {
            if (n == 1)
            {
                yield return Tuple.Create(1, 1);
            }
            else
            {
                int i = 2;
                while (n > 1)
                {
                    if (n % i == 0)
                    {
                        int index = 0;
                        while (n % i == 0)
                        {
                            index++;
                            n /= i;
                        }
                        yield return Tuple.Create(i, index);
                    }
                    i++;
                }
            }
        }
    }
}

Answer: 76576500