# Project Euler Problem 7

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 (

**::**)!

## Trackbacks & Pingbacks