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

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?

Answer

76576500

---

Python

#!/usr/bin/env python
import math
from collections import defaultdict
from functools import reduce

def factorize(n):
    if n < 1:
        raise ValueError('fact() argument should be >= 1')
    if n == 1:
        return []  # special case
    res = []
    # iterate over all even numbers first.
    while n % 2 == 0:
        res.append(2)
        n //= 2
    # try odd numbers up to sqrt(n)
    limit = math.sqrt(n + 1)
    i = 3
    while i <= limit:
        if n % i == 0:
            res.append(i)
            n //= i
            limit = math.sqrt(n + i)
        else:
            i += 2
    if n != 1:
        res.append(n)
    return res

_triangle_cache = {1: 1}
def triangle(n):
    if n < 1:
        return 0
    try:
        return _triangle_cache[n]
    except KeyError:
        result = n + triangle(n - 1)
        _triangle_cache[n] = result
        return result

def num_divisors(n):
    factors = sorted(factorize(n))
    histogram = defaultdict(int)
    for factor in factors:
        histogram[factor] += 1
    # number of divisors is equal to product of 
    # incremented exponents of prime factors
    from operator import mul
    try:
        return reduce(mul, [exponent + 1 for exponent in list(histogram.values())])
    except:
        return 1

triangles = (triangle(i) for i in range(1, 100000))
divisible_triangles = (i for i in triangles if num_divisors(i) > 500)
print(next(divisible_triangles))

---

Ruby

#!/usr/bin/env ruby
require 'mathn' 

class Integer 
  def divisors
    return [1] if self == 1
    primes, powers = self.prime_division.transpose 
    exponents = powers.map{|i| (0..i).to_a} 
    divisors = exponents.shift.product(*exponents).map do |powers| 
      primes.zip(powers).map{|prime, power| prime ** power}.inject(:*) 
    end 
    divisors.sort.map{|div| [div, self / div]} 
  end
end

triangles = Enumerator.new do |yielder|
  i = 1
  loop do
    yielder.yield i * (i + 1) / 2
    i += 1
  end
end

puts triangles.detect { |t| t.divisors.count > 500 }

---

Haskell

import Data.List (group)

triangles :: [Int]
triangles = scanl1 (+) [1..]

primes :: [Int]
primes = sieve [2..] where
    sieve [] = []
    sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]

factorize :: Int -> [Int]
factorize n = primeFactors n primes where
    primeFactors 1 _ = []
    primeFactors _ [] = []
    primeFactors m (p:ps) | m < p * p = [m]
                          | r == 0 = p : primeFactors q (p:ps)
                          | otherwise = primeFactors m ps
                          where (q, r) = quotRem m p

primePowers :: Int -> [(Int, Int)]
primePowers n = [(head x, length x) | x <- group $ factorize n]

numDivisors :: Int ->  Int
numDivisors n = product [k + 1 | (_, k) <- primePowers n]

main :: IO ()
main = print $ head $ dropWhile (\n -> numDivisors n <= 500) triangles

---

Clojure

#!/usr/bin/env clojure 
(defn divisor? [b n]
  (= (rem n b) 0))

(defn triangle-number [n]
  (cond 
    (< n 1) nil
    (= n 1) 1
    :else (+ n (triangle-number (dec n)))))

(defn divisors [n]
  (cons n (filter #(divisor? % n) (range 1 (inc (/ n 2))))))


(defn num-divisors [n])

(def triangle-numbers (map triangle-number (range 1 1000)))
(println (first (filter #(> (num-divisors %) 500) triangle-numbers)))

---

Java

public final class p012 implements EulerSolution {
	
	public static void main(String[] args) {
		System.out.println(new p012().run());
	}
	
	
	/* 
	 * Computers are fast, so we can implement this solution directly without any clever math.
	 */
	public String run() {
		int triangle = 0;
		for (int i = 1; ; i++) {
			if (Integer.MAX_VALUE - triangle < i)
				throw new ArithmeticException("Overflow");
			triangle += i;  // This is the ith triangle number, i.e. num = 1 + 2 + ... + i = i * (i + 1) / 2
			if (countDivisors(triangle) > 500)
				return Integer.toString(triangle);
		}
	}
	
	
	// Returns the number of integers in the range [1, n] that divide n.
	private static int countDivisors(int n) {
		int count = 0;
		int end = Library.sqrt(n);
		for (int i = 1; i < end; i++) {
			if (n % i == 0)
				count += 2;
		}
		if (end * end == n)  // Perfect square
			count++;
		return count;
	}
	
}

---

Mathematica

(* We do a straightforward search with some help from built-in functions. *)
TriangleNumber[n_] = Sum[i, {i, n}];
i = 1;
While[DivisorSigma[0, TriangleNumber[i]] <= 500, i++]
TriangleNumber[i]