Project Euler — Problem 78 Solution

Problem

Let p(n) rep­re­sent the num­ber of dif­fer­ent ways in which n coins can be sep­a­rat­ed into piles. For exam­ple, five coins can sep­a­rat­ed into piles in exact­ly sev­en dif­fer­ent ways, so p(5)=7.

OOOOO

OOOO   O

OOO   OO

OOO   O   O

OO   OO   O

OO   O   O   O

O   O   O   O   O

Find the least val­ue of n for which p(n) is divis­i­ble by one mil­lion.

Solution

// the pentagonal numbers sequence, i.e. 1, 2, 5, 7, 12, 15, 22, ...
let pentagonalNumbers =
    Seq.unfold (fun state -> Some(state, state+1)) 1
    |> Seq.collect (fun n -> [n; -1*n])
   |> Seq.map (fun n -> int(0.5 * double(n) * double(3 * n - 1)))

// the coefficients sequence, i.e. +, +, -, -, +, +, -, -, ...
let pCoefficients =
    Seq.unfold (fun state -> Some(state, -1*state)) 1 |> Seq.collect (fun n -> [n; n])

// cache results to improve performance
let mutable cache = Array.init 100000 (fun n -> if n = 0 then 1I else 0I)

// define the function p using the pentagonal numbers
let rec p k =
    if cache.[k] <> 0I then cache.[k]
    else
        let pSeq =
            pentagonalNumbers
            |> Seq.map (fun n -> k - n)
            |> Seq.takeWhile (fun n -> n >= 0)
            |> Seq.map p
        let pk =
            pCoefficients
            |> Seq.zip pSeq
            |> Seq.sumBy (fun (pk, coe) -> pk * bigint(coe))
        cache.[k] <- pk
        pk

let answer =
    Seq.unfold (fun state -> Some(state, state+1)) 1
    |> Seq.filter (fun k -> (p k) % 1000000I = 0I)
    |> Seq.head

Well, this one took some thought and some time to come up with a solu­tion which runs under a minute! A brute force approach sim­ply wouldn’t have worked here as p(k) becomes very large very quick­ly (p(200) = 3972999029388…). Thank­ful­ly, as the wiki page on par­ti­tion points out, you can build a recur­rence for the func­tion p such that:

p(k) = p(k — 1) + p(k — 2) — p(k — 5) — p(k — 7) + p(k — 12) + p(k — 15) — p(k — 22) — …

using pen­tag­o­nal num­bers in the form of

image

for n run­ning over pos­i­tive and neg­a­tive inte­gers (n = 1, –1, 2, –2, 3, –3, …), gen­er­at­ing the sequence 1, 2, 5, 7, 12, 15, 22, … The signs in the sum­ma­tion con­tin­ue to alter­nate +, +, –, –, +, +, …

Using dynam­ic pro­gram­ming tech­nique, I’m caching the val­ue of p(k) as they’re gen­er­at­ed and in doing so, enabled this solu­tion to run in under 30 sec­onds.