The Problem

Pentagonal numbers are generated by the formula, P_n=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P₄ + P₇ = 22 + 70 = 92 = P₈. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_j and P_k, for which their sum and difference are pentagonal and D = |P_k − P_j| is minimised; what is the value of D?

The Solution

I like it when the problem spells out the main function we're going to need to find the solution. So let's start with that:

let p n = n * (3 * n - 1) / 2

I lack the math skills to choose a good upper bound for this one, so I'll arbitrarily choose 10000. If we find we don't get the right answer, we can adjust it later.

[<Literal>]
let maxN = 10000

We we really need to get going is an array of pentagonal numbers that we can pair up. So let's take the first 10000 pentagonal numbers and stuff them in an array.

let pentagonalNumbers = 
    Seq.unfold (fun state -> Some(p state, state + 1)) 1
    |> Seq.take maxN
    |> Array.ofSeq

And since we need to test our results to see if they are pentagonal, we can use that same array to build a map that we can use to test our results for pentagonality. (Is that a word? If not, it should be.)

let pentagonalMap = 
    pentagonalNumbers 
    |> Seq.map (fun x-> (x,x)) 
    |> Map.ofSeq

let isPentagonal n = 
    Map.containsKey n pentagonalMap

To solve the problem, we'll start by pairing up our pentagonal numbers with other pentagonal numbers.

let combos = [
    for j in 0..(maxN-2) do
        for k in (j+1)..(maxN-1) -> 
            (pentagonalNumbers.[j],pentagonalNumbers.[k])
]

combos pairs up j values (all pentagonal numbers except the last one) with k values (all pentagonal numbers greater than the j value). This ensures that P_k - P_j is always positive and that j and k are never equal.

Now we can solve the problem:

combos
|> List.filter (fun (j,k) -> isPentagonal (j + k) && isPentagonal (k - j))
|> List.map (fun (j,k) -> k - j)
|> List.min

We filter out combos for which j+k is not pentagonal or k-j is not pentagonal. Then we map the filters pairs to k-j. The minimum value of k-j is the answer.

Other Posts in This Series