Skip to content

Project Euler Problem 77

February 26, 2012

Project Euler Problem 77 solution is not difficult if we “stand on the shoulders” of previous solutions.

Using solution to Project Euler Problem 76 it is easy to come up with a generalization function that, being given a target number and list of allowed parts, returns back overall number of partitions of target using given parts. Also using solution to Project Euler Problem 10 we can produce sequence of primes.

The only missing piece is a one-liner function that, given a target number, returns back sequence of primes that are good for performing partitioning of the target. Assembling all this together we get:

let rec primes = 
    Seq.cache <| seq { yield 2; yield! Seq.unfold nextPrime 3 }
and nextPrime n =
    if isPrime n then Some(n, n + 2) else nextPrime(n + 2)
and isPrime n =
    if n >= 2 then
        |> Seq.tryFind (fun x -> n % x = 0 || x * x > n)
        |> fun x -> x.Value * x.Value > n
    else false

// Partition from prime parts
let parts target =
    primes |> Seq.takeWhile ((>=) (target - 2)) |> Seq.toArray

// Partitioning counter from Problem 76
let partitions target (parts: int[]) =
    let ways = Array.zeroCreate (target + 1)
    ways.[0] <- 1
    for i in 0..(parts.Length - 1) do
        for j in parts.[i] do
            ways.[j] <- ways.[j] + ways.[j - parts.[i]]

let problem077 () =
    Seq.initInfinite id
    |> Seq.find (fun x -> partitions x (parts x) > 5000)

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: