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

This has been the most sophisticated problem yet.

My first solution took 2 minutes to write, but I gave up on it after 5 minutes of running.

let problem12a = 
    let divisors n = seq {for i in 1..n/2 do if n % i = 0 then yield i}
    let rec find i last = 
        if last |> divisors |> Seq.length > 500 then last
        else find (i+1) (last+(i+1))
    find 1 1

Then I realized I had a fast function for building a list of prime factors from Problem 3 which I could use to generate a list of all divisors.  I abused that into giving me the answer in about 1 minute.

let problem12b =
    let divisors n =
        let rec divisors n j list = 
            if n = 1I then list
            elif n % j = 0I then divisors (n/j) 2I (list @ j::(list |> List.map (fun x -> x*j)))
            else divisors n (j + 1I) (list)
        1I::(divisors n 2I []) |> List.toSeq |> Seq.distinct
        
    let rec find i last = 
        if last |> divisors |> Seq.length > 500 then last
        else find (i+1I) (last+(i+1I))
    find 1I 1I

But then I remembered my Number Theory days.  Given a prime factorization p1**n1…p2**n2…p3**n3… the number of divisors is equal to (n1 + 1)*(n2 + 1)*(n3 + 1)*…

let problem12c =
    let factorize n =
        let rec factorize n j list = 
            if n = 1 then list
            elif n % j = 0 then factorize (n/j) 2 (j::list)
            else factorize n (j + 1) (list)
        factorize n 2 []
    
    let countDivisors n =
        let rec countDivisors flist count =
            match flist with 
            | [] -> count
            | f::list -> 
                let plist = list |> List.partition (fun i -> i = f)
                countDivisors (snd plist) (((fst plist |> List.length)+2)*count)
        countDivisors (factorize n) 1

    let rec find i last = 
        if last |> countDivisors > 500 then last
        else find (i+1) (last+(i+1))
    find 1 1

That gave me the answer in less than a second.

Here’s another version of (c) using Seq.groupBy instead of recursively apply List.partition.  It runs in about the same amount of time.

let problem12d =
    let factorize n =
        let rec factorize n j list = 
            if n = 1 then list
            elif n % j = 0 then factorize (n/j) 2 (j::list)
            else factorize n (j + 1) (list)
        factorize n 2 []
    
    let countDivisors n =
        factorize n
        |> Seq.groupBy id
        |> Seq.fold (fun acc (f,s) -> ((Seq.length s) + 1)*acc) 1

    let rec find i last = 
        if last |> countDivisors > 500 then last
        else find (i+1) (last+(i+1))
    find 1 1