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]
= scanl1 (+) [1..]
triangles
primes :: [Int]
= sieve [2..] where
primes = []
sieve [] :xs) = p : sieve [x | x <- xs, x `mod` p > 0]
sieve (p
factorize :: Int -> [Int]
= primeFactors n primes where
factorize n 1 _ = []
primeFactors = []
primeFactors _ [] :ps) | m < p * p = [m]
primeFactors m (p| r == 0 = p : primeFactors q (p:ps)
| otherwise = primeFactors m ps
where (q, r) = quotRem m p
primePowers :: Int -> [(Int, Int)]
= [(head x, length x) | x <- group $ factorize n]
primePowers n
numDivisors :: Int -> Int
= product [k + 1 | (_, k) <- primePowers n]
numDivisors n
main :: IO ()
= print $ head $ dropWhile (\n -> numDivisors n <= 500) triangles main
$ 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:
2)
res.append(//= 2
n # try odd numbers up to sqrt(n)
= math.sqrt(n + 1)
limit = 3
i while i <= limit:
if n % i == 0:
res.append(i)//= i
n = math.sqrt(n + i)
limit else:
+= 2
i if n != 1:
res.append(n)return res
= {1: 1}
_triangle_cache def triangle(n):
if n < 1:
return 0
try:
return _triangle_cache[n]
except KeyError:
= n + triangle(n - 1)
result = result
_triangle_cache[n] return result
def num_divisors(n):
= sorted(factorize(n))
factors = defaultdict(int)
histogram for factor in factors:
+= 1
histogram[factor] # 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
= (triangle(i) for i in range(1, 100000))
triangles = (i for i in triangles if num_divisors(i) > 500)
divisible_triangles 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
= self.prime_division.transpose
primes, powers = powers.map{|i| (0..i).to_a}
exponents = exponents.shift.product(*exponents).map do |powers|
divisors .zip(powers).map{|prime, power| prime ** power}.inject(:*)
primesend
.sort.map{|div| [div, self / div]}
divisorsend
end
= Enumerator.new do |yielder|
triangles = 1
i loop do
.yield i * (i + 1) / 2
yielder+= 1
i 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 {
+= 1;
result } else {
+= 2;
result }
}
}
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