## 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:

$\displaystyle 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?

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.028s user 0m0.024s 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.530s
user   0m0.524s
sys    0m0.000s

## 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.648s
user   0m1.620s
sys    0m0.000s