# Project Euler – Problem 12 Solution

#### Problem

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?

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

naturalNumbers
|> Seq.map (fun x -> triangleNumber(x))
|> Seq.filter (fun x -> Seq.length(findFactorsOf(x)) >= 500)
```

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.

### 2 thoughts on “Project Euler – Problem 12 Solution”

1. mine 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

2. also, 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