Claudio Cherubino's blog Life of a Googler

Project Euler in F# – Problem 45

A long time has passed since I last posted the solution of one of Project Euler's problems.

Problem 45 is related to figurate numbers, i.e. numbers that can be represented as geometrical patterns.

In particular, we are going to find a number that is triangular, pentagonal and hexagonal at the same time:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle: Tn=n(n+1)/2
Pentagonal: Pn=n(3n?1)/2
Hexagonal: Hn=n(2n?1)

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

A trivial solution will be computing the lists of triangular, pentagonal and hexagonal numbers and then find their intersection. However, we don't know how big the searched number can be, so we are not able to determine when to stop the generation of each list.

Hence we need a smarter solution, based on the mathematical properties of these numbers.

First of all, every hexagonal number is also a triangular number, so our problem is reduced to finding the smallest hexagonal pentagonal number greater than 40755.

Then we can generate the hexagonal numbers and check whether they are also pentagonal, stopping at the first one found.

According to the definition, we can test if a positive integer x is a pentagonal number by computing:

If n is an integer, then x is the nth pentagonal number. If n is not an integer, then x is not pentagonal.

Let's look at the F# code:

#light
open System
open Microsoft.FSharp.Math.BigInt

let hexagonal n = n * (2I * n - 1I)
let isPentagonal x = ((sqrt(to_float (24I * x + 1I)) + 1.0) % 6.0) = 0.0

let nums = 144I |> Seq.unfold (fun i -> Some (i, i + 1I))
let answer = nums |> Seq.map hexagonal |> Seq.find isPentagonal

At lines 5 and 6 we define the functions to compute the nth hexagonal number and to check if an integer x is pentagonal.

Then we start generating the hexagonal numbers to be tested, starting from the 144th, since the solution must be greater than 40755, that is the 143th hexagonal number.

In the last line we just return the first number for which isPentagonal is true, without having to know when to stop thanks to lazy evaluation, which allows us to continue generating numbers only when actually needed.

The solution to the problem is greater than I could imagine, that's why we need to use BigInt instead of normal integers.

What do you think about the approach I followed to solve this problem?