60 Days of Euler in F# - Problem 12

The 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?

The Solution

This one is a little tricky. Note that the factor examples the problem definition specifies include composite numbers (i.e., multiples of more than one prime). In most of the Euler problems I’ve worked on, factors are limited to primes.

Thus, to find the number of divisors for n, we need to check all numbers up to the square root of n.

let intsqrt i = int(sqrt(float i))

let numDivisors n =

    let factorsOver3() =
        let sr = intsqrt n
        seq { 3..sr }
        |> Seq.filter (fun e -> n % e = 0)
        |> Seq.length

    match n with
    | 1 -> 1
    | 2 -> 2
    | x when (x &&& 1) = 0 -> (2 + factorsOver3()) * 2
    | _ -> (1 + factorsOver3()) * 2
  • If n is 1, then there’s only 1 divisors
  • If n is 2, there’s 2 divisors (1 and 2)
  • If n is even, the number of divisors is 2 (2 and n itself) plus the number of factors it has > 3, times 2. Why do we multiply by two? Because if we only test up to the square root of n, then if we find a factor then n/x is also a factor.
  • If n is odd, the number of divisors is 1 (the number 1 is a divisor) plus the number of factors over 3. We also multiply by two for the same reason as in the even case.

With that in hand, we can look for the solution:

let rec getOver500 t n =
    if numDivisors t >= 500 then
        t
    else
        getOver500 (t + n + 1) (n + 1)

getOver500 1 1

The getOver500 function takes two parameters, t which is the accumulator for the triangle number value, and n which is the nth natural number. If it finds a t with >= 500 divisors, it returns t, otherwise it computes the next triangle number (t + n + 1) and the next natural number (n + 1) and recurses.

Full disclosure: While I was writing this blog post, I discovered a very subtle bug. The code finds the correct answer to this problem, but it is flawed. Consider the case of 36. 36 has 9 divisors (1, 2, 3, 4, 6, 9, 12, 18, and 36) but numDivisors actually returns 10 for that. The numDivisors function, as written, will always return an even number, even though that is (in hindsight) clearly wrong. I’m leaving it here as a reminder that just because code works today, that doesn’t mean you won’t find a bug tomorrow when the inputs are different.

Looking back, I see that I was trying to be too clever by considering different cases for odd and even. There is a much simpler way that executes in almost exactly the same amount of time. Just replace the numDivisors function with this one:

let numDivisors n =
    let sr = intsqrt n
    seq { 1..sr }
    |> Seq.filter (fun e -> n % e = 0)
    |> Seq.collect (fun e -> [e; n/e])
    |> Seq.distinct
    |> Seq.length
Other Posts in This Series