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
        primes 
        |> 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]..target do
            ways.[j] <- ways.[j] + ways.[j - parts.[i]]
    ways.[target]

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

From → Project Euler

Leave a Comment

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: