# Project Euler Problem 78

Project Euler Problem 78 solution can be based on Partition function value. Using Euler’s generating function at (11) of the above reference we may for each sequential natural **n** calculate number of partitions based on pre-cached number of partitions for lesser numbers until one occurs that is divisible by 1000000. As number of partitions may require manipulating with BigNum before we find the sought number we can stay within integer space by dealing with remainders **n mod 1000000** instead of dealing with **n**:

let problem078 () = let ``P(n)`` (cache: int[]) n = let rec ``while/break`` k = if k <= n then let idx1 = n - k * (3 * k - 1) / 2 let idx2 = n - k * (3 * k + 1) / 2 if idx1 >= 0 || idx2 >= 0 then let sign = if k%2 = 0 then -1 else 1 if idx1 >= 0 then cache.[n] <- cache.[n] + sign*cache.[idx1] if idx2 >= 0 then cache.[n] <- cache.[n] + sign*cache.[idx2] cache.[n] <- cache.[n] % 1000000 ``while/break`` (k + 1) ``while/break`` 1 cache.[n] let cache = Array.zeroCreate 100000 cache.[0] <- 1 Seq.initInfinite id |> Seq.find (fun n -> ``P(n)`` cache n = 0)

Interestingly, the code above implements action that is similar to use of **break** operator in imperative languages via the use of a tail-recursive function.

Advertisements

Leave a Comment