# Project Euler Problem 12 Solution

## 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.029s user 0m0.028s 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.449s
user   0m0.448s
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.515s user 0m1.512s 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.242s
user   0m0.240s
sys    0m0.000s