Skip to content

Project Euler Problem 7

October 10, 2011

Project Euler Problem 7 makes me uneasy about Solver composition: we assumed so far selector part performs takeWhile type of selection, however in this case skipWhile type of selection better fits for the purpose. The matter to think about, although it is not that hard to perform selection on the aggregator side.

We will generate a sequence of primes until 10001st number comes out, keeping already found primes in a list and for each next prime going up by odd numbers until such that being divided by any of lesser primes from the list yields a non-zero remainder.

let primes =
    let rec findNextPrime maybePrime lesserPrimes =
        match List.tryFind(fun x -> maybePrime % x = 0) lesserPrimes with
        | Some _ -> findNextPrime (maybePrime + 2) lesserPrimes
        | None -> maybePrime

    Seq.append {2..3}
        (Seq.unfold (fun (lastPrime, lessOrEqPrimes) ->
            let nextPrime = findNextPrime (lastPrime + 2) lessOrEqPrimes
            Some (nextPrime, (nextPrime, nextPrime::lessOrEqPrimes)))
                (3,[3;2]))

let problem007 () =
    primes
    |> solve PassAll PassAll (Seq.skip 10000 >> Seq.head)

The matter I’m unsure about is how would it better to arrange primes list: in ascending or descending order? If it is ascending we supposedly will reject non-primes quicker, but will spend time on appending to the end of the list. Otherwise inserting a next prime into the list is a trivial cons, but rejecting non-primes may take more scanning thru the list. In order to find out which approach would perform better we should measure performance of both implementations for primes, with ascending and with descending order of members:

let primesA =
    let rec findNextPrime maybePrime lesserPrimes =
        match List.tryFind(fun x -> maybePrime % x = 0) lesserPrimes with
        | Some _ -> findNextPrime (maybePrime + 2) lesserPrimes
        | None -> maybePrime

    Seq.append {2..3}
        (Seq.unfold (fun (lastPrime, lessOrEqPrimes) ->
            let nextPrime = findNextPrime (lastPrime + 2) lessOrEqPrimes
            Some (nextPrime, (nextPrime, lessOrEqPrimes @ [nextPrime])))
                (3,[3]))

let problem007 () =
    primesA |> (Seq.skip 10000 >> Seq.head)

It comes out that inplementation with ascending order of members that uses infamous append (@) operator on lists is at least twice faster that one with descending order that uses cons (::)!

Advertisements

From → Project Euler

One Comment

Trackbacks & Pingbacks

  1. Project Euler Problem 10 « In F# Major

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: