#### Problem

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^{th}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?

#### Solution

open System let triangleNumber(n:int64) = [1L..n] |> Seq.sum let findFactorsOf(n:int64) = let upperBound = int64(Math.Sqrt(double(n))) [1L..upperBound] |> Seq.filter (fun x -> n % x = 0L) |> Seq.collect (fun x -> [x; n/x]) let naturalNumbers = Seq.unfold (fun x -> Some(x, x+1L)) 1L let answer = naturalNumbers |> Seq.map (fun x -> triangleNumber(x)) |> Seq.filter (fun x -> Seq.length(findFactorsOf(x)) >= 500) |> Seq.head

My solution here is simple, first create the *triangleNumber* function that calculates the triangle number for a given natural number.

I then created a modified version of the *findFactorsOf* function I first used in the problem 3 solution to find ALL the factors of a number including 1 and itself.

Again I used Seq.unfold to build up a sequence of natural numbers and to find the answer I iterate through the natural numbers and for each get its triangle number; find the factors of the triangle number; and check if the number of factors is at least 500.

Omumine is a bit more optimal, cuz I don’t start summing from 1 all the time but from previous triangle number, I also have a printf to see the process

let p12 =

let factors number =

let ff = seq {

for divisor in 1 .. (float >> sqrt >> int) number do

if number % divisor = 0 then

yield divisor

yield number / divisor

}

ff|> Seq.distinct

let rec loop i tri fc =

printf “%A %A %A \n” i tri fc

match fc with

| x when x > 500 -> tri

| x -> loop (i+1) (tri+i+1) ((factors (tri+i+1)) |> Seq.length)

loop 1 1 1

Omualso, when you find factors you don’t have to go from 1 to upperbound but from 1 to sqrt(upperbound)

and when you get n%i = 0 you add to he factors collection both n and i