Skip to content

Project Euler Problem 78

March 2, 2012

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

From → F#, 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: