Project Euler – Problem 78 Solution

Problem

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different 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 value of n for which p(n) is divisible by one million.

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 solution which runs under a minute! A brute force approach simply wouldn’t have worked here as p(k) becomes very large very quickly (p(200) = 3972999029388…). Thankfully, as the wiki page on partition points out, you can build a recurrence for the function 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 pentagonal numbers in the form of

for n running over positive and negative integers (n = 1, –1, 2, –2, 3, –3, …), generating the sequence 1, 2, 5, 7, 12, 15, 22, … The signs in the summation continue to alternate +, +, –, –, +, +, …

Using dynamic programming technique, I’m caching the value of p(k) as they’re generated and in doing so, enabled this solution to run in under 30 seconds.