Project Euler in F#: Problem 12

I’m skipping problem 11 for now, since I can’t think of an elegant way to do it, and writing out the ‘C’ style solution I have in my head doesn’t seem like an interesting exercise. Any suggestions? Anyway, on to problem 12:

What is the value of the first triangle number to have over five hundred divisors?

module Problem12 =
    let triangleNumbers = Seq.initInfinite (fun n -> (n+2) * (n+3) / 2) //skip the first triangle number (1), to avoid having to deal with an edge case in numFactors

    //could probably speed this up a lot by pre-calculating prime factors (maybe using a LazyList)
    let factors n =
        let rec loop n m ms =
            if n % m = 0 then
                loop (n/m) m (m::ms)
            elif n > m then
                loop n (m+1) ms
            else
                ms
        loop n 2 []

    let numFactors n = factors n |> Seq.countBy(fun x->x) |> Seq.map (fun (a,b) -> b+1) |> Seq.reduce(*)

    let ans = Seq.find (fun x -> numFactors x > 500) triangleNumbers;;

Like problem 10, this is trivial, given the solution to a previous problem. I ended up re-writing the factors function from problem 3, because the old function needed to handle 64 bit values, and this doesn’t. There’s a nice stackoverflow answer on how to do this generically; I may give that a shot in the future, but this solution is good enough for now :-).

Advertisements
Project Euler in F#: Problem 12

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s