Project Euler — Problem 12 Solution

Problem

The sequence of tri­an­gle num­bers is gen­er­at­ed by adding the nat­ur­al num­bers. So the 7th tri­an­gle num­ber 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 fac­tors of the first sev­en tri­an­gle num­bers:

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 tri­an­gle num­ber to have over five divi­sors.

What is the val­ue of the first tri­an­gle num­ber to have over five hun­dred divi­sors?

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 solu­tion here is sim­ple, first cre­ate the tri­an­gleNum­ber func­tion that cal­cu­lates the tri­an­gle num­ber for a giv­en nat­ur­al num­ber.

I then cre­at­ed a mod­i­fied ver­sion of the find­Fac­tor­sOf func­tion I first used in the prob­lem 3 solu­tion to find ALL the fac­tors of a num­ber includ­ing 1 and itself.

Again I used Seq.unfold to build up a sequence of nat­ur­al num­bers and to find the answer I iter­ate through the nat­ur­al num­bers and for each get its tri­an­gle num­ber; find the fac­tors of the tri­an­gle num­ber; and check if the num­ber of fac­tors is at least 500.