The Problem

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle T_n=n(n+1)/2 1, 3, 6, 10, 15, ...

Pentagonal P_n=n(3n−1)/2 1, 5, 12, 22, 35, ...

Hexagonal H_n=n(2n−1) 1, 6, 15, 28, 45, ...

It can be verified that T₂₈₅ = P₁₆₅ = H₁₄₃ = 40755.

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

The Solution

Plan of attack:

• Starting from 286, generate a sequence of triangle numbers
• Test each one for pentagonality
• Test each one for hexagonality
• When we find one that is both pentagonal and hexagonal, we have our answer.

Let's start with the easy stuff:

let firstT = 285L + 1L
let firstP = 165L + 1L
let firstH = 143L + 1L

Based on the problem definition, we know that the first time T, P, and H line up is at n = 285, 165, and 143, respectively. So when we start generating sequences, we're going to start at one past those.

let t n = n * (n + 1L) / 2L
let p n = n * (3L * n - 1L) /2L
let h n = n * (2L * n - 1L)

The above trio of functions generate the nth triangle, pentagonal, and hexagonal number.

Now, we need a quick way to test for pentagonal and hexagonal numbers. So we'll make maps containing 100000 of each class of numbers. 100000 is a number I just made up on the spot because it "seemed reasonable". We can adjust later if need be.

let makeMap f first =
    let nums =
        Seq.unfold (fun state -> Some(f state, state + 1L)) first
        |> Seq.mapi (fun i x -> (x,i+1))
        |> Seq.take 100000
        |> List.ofSeq

    let max = fst (nums |> List.last)
    let map = Map.ofList nums
    (max,map)

let pentagonalMax,pentagonalMap = makeMap p firstP
let hexagonalMax,hexagonalMap = makeMap h firstH
let maxToCheck = min pentagonalMax hexagonalMax

let isPentagonal n = Map.containsKey n pentagonalMap
let isHexagonal n = Map.containsKey n hexagonalMap

The makeMap function takes a starting value and a sequence unfolding function. It generates the sequence and converts it into a map. It returns both the maximum value in the map and the map itself.

Using makeMap we generate pentagonal and hexagonal maps and their maximums. The value maxToCheck gets bound to the minimum of pentagonalMax and hexagonalMax. We'll stop generating triangle numbers when they get above this value.

Finally, we have a pair of functions, isPentagonal and isHexagonal that can check for pentagonality and hexagonality, respectively.

Now we need a bunch of triangle numbers to start testing:

let generateTriangle state =
    let number = t state
    if (number > maxToCheck) then
        None
    else
        Some(number, state + 1L)

let triangleNumbers =  Seq.unfold generateTriangle firstT

We use Seq.unfold to generate triangle numbers using the generator function generateTriangle. It stops generating when the number generated exceeds maxToCheck.

Now we can solve the problem:

triangleNumbers
|> Seq.filter (fun n -> isPentagonal n && isHexagonal n)
|> Seq.head

We simply take our sequence of triangle numbers, filter out any that aren't both pentagonal and hexagonal, and return the head of that sequence. That is the answer.

Other Posts in This Series