Skip to main content

Project Euler #012

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?

let rec triangle_number order =
    if order = 0 then order else order + triangle_number (order - 1)

let rec get_divisors n (i:int) (divisors:list<int>) =
    if i < (n / 2) then
        if (n % i) = 0 then
            get_divisors n (i + 1) (i :: divisors)
        else
            get_divisors n (i + 1) divisors
    else
        divisors

let rec find_triangle_number order number_of_divisors =
    let divisors = (get_divisors (triangle_number order) 1 []).Length
    if divisors > number_of_divisors then
        order
    else
        find_triangle_number (order + 1) number_of_divisors

// This is an expensive operation
(find_triangle_number 1 500) |> triangle_number
comments powered by Disqus