# Project Euler Problem 77

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

Leave a Comment