Question

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?

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

$ ghc -O2 -o triangle-numbers triangle-numbers.hs
$ time ./triangle-numbers
real   0m0.026s
user   0m0.026s
sys    0m0.000s

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))

$ time python3 triangle-numbers.py
real   0m0.345s
user   0m0.329s
sys    0m0.016s

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 }

$ time ruby triangle-numbers.rb
real   0m1.428s
user   0m1.427s
sys    0m0.000s

Rust

fn num_divisors(n: u64) -> u64 {
    let mut result = 0;
    let max = (n as f64).sqrt() as u64;
    for i in 1..max + 1 {
        if n % i == 0 {
            if n / i == i {
                result += 1;
            } else {
                result += 2;
            }
        }
    }
    return result;
}

fn main() {
    let triangles = (1..).scan(0, |triangle, n| {
        *triangle += n;
        Some(*triangle)
    });
    let first = triangles
        .skip_while(|&triangle| num_divisors(triangle) <= 500)
        .next()
        .unwrap();
    println!("{}", first);
}

$ rustc -C target-cpu=native -C opt-level=3 -o triangle triangle.rs
$ time ./triangle
real   0m0.219s
user   0m0.219s
sys    0m0.000s