Project Euler — Problem 44 Solution

Problem

Pen­tag­o­nal num­bers are gen­er­at­ed by the for­mu­la, Pn=n(3n-1)/2. The first ten pen­tag­o­nal num­bers are:

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

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. How­ev­er, their dif­fer­ence, 70 — 22 = 48, is not pen­tag­o­nal.

Find the pair of pen­tag­o­nal num­bers, Pj and Pk, for which their sum and dif­fer­ence is pen­tag­o­nal and D = |Pk — Pj| is min­imised; what is the val­ue of D?

Solution

open System.Collections.Generic

// define the Pentagonal function P
let P n = n*(3*n-1)/2

// use a dictionary as cache
let mutable cache = new Dictionary<int, int>()
[1..5000] |> List.iter (fun n -> cache.[n] <- P n)

// function to check if a number is pentagonal by looking at the cached values
let isPentagonal n = cache.ContainsValue n

// predicate function to check if Pk and Pj's sum and diff are both pentagonal
let predicate (k, j) =
    let pk = cache.&#91;k&#93;
    let pj = cache.&#91;j&#93;
    isPentagonal (pj + pk) && isPentagonal (pk - pj)

// the sequence of k, j pairs to check
let kjSeq =
    &#91;1..5000&#93;
    |> List.collect (fun k -> [1..k-1] |> List.rev |> List.map (fun j -> (k, j)))

// get the first pair of k, j whose sum and difference are both pentagonal
let (k, j) = kjSeq |> Seq.filter predicate |> Seq.head

let answer = (P k) - (P j)

Hav­ing exper­i­ment­ed with a few alter­na­tive imple­men­ta­tions which did not use a muta­ble dic­tio­nary and wait­ed impa­tient­ly for the code to nev­er return I set­tled on this solu­tion which caches the first 5000 val­ues in the pen­tag­o­nal num­ber sequence for quick lookup lat­er on in the solu­tion.

Going into more detail about the solu­tion itself, to ensure |Pk — Pj| is min­imised, the val­ue of k and the dif­fer­ence between k and j must be min­imised too as the fur­ther apart Pk and Pj are in the pen­tag­o­nal sequence the big­ger their dif­fer­ence will be and the big­ger k is the big­ger Pk will be too.

The rest of the algo­rithm here is sim­ple, for each val­ue k (between 1 and 5000, being the size of the cache) check for each j where 1 <= j < k, start­ing from the biggest j, if the sum and dif­fer­ence of Pk and Pj are both pen­tag­o­nal. The first k and j which sat­is­fy this pred­i­cate will have the small­est dif­fer­ence between Pk and Pj.