Why is this F# code slower than the C# equivalent?

Question

I'm tackling the Project Euler problems again (did the 23 first ones before when I was learning C#) and I'm quite baffled at the subpar performance of my solution to problem 5.

It reads as follow:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Now my incredibly primitive brute-force solution of C# tugs through this problem in roughly 25 seconds.

var numbers = Enumerable.Range(1, 20);
int start = 1;
int result;
while (true)
{
   if (numbers.All(n => start % n == 0))
   {
       result = start;
       break;
   }
   start++;
}

Now my F# solution uses brute forcing as well but at least it does a bit more discrimination and such so that it "should" in my mind run faster but it clocks out at ~45 secs so it's nearly twice as slow as the C# one.

let p5BruteForce =
    let divisors = List.toSeq ([3..20] |> List.rev)
    let isDivOneToTwenty n =
        let dividesBy = 
            divisors |> Seq.takeWhile(fun x -> n % x = 0)                
        Seq.length dividesBy = Seq.length divisors

    let findNum n =
        let rec loop n = 
            match isDivOneToTwenty n with
            | true -> n
            | false -> loop (n + 2)
        loop n
    findNum 2520

P.S - I know that my solution could be better, in this case I am simply wondering how it could be that a better brute-force solution can be so much slower than a primitive one.

Answer 1

You can use List.forall instead of converting to a seq and then doing Seq.length:

let divisors = [3..20] |> List.rev
let isDivOneToTwenty n = divisors |> List.forall (fun d -> n % d = 0)

Seq.length will need to traverse the entire sequence to determine the number of elements, while forall can return as soon as an element fails the predicate.

you can also write findNum as:

let rec findNum n = if isDivOneToTwenty n then n else findNum (n + 2)

Answer 2

Even a more direct translation such as

let numbers = { 1..20 }
let rec loop start =
    if numbers |> Seq.forall (fun n -> start % n = 0) 
    then start
    else loop (start + 1)
loop 1

takes a minute and a half (your C# version takes 25 seconds on my machine too). The numeric sequence seems to be the culprit as changing it to an array ([| 1..20 |]) and using Array.forall drops it to 8 secs. The C# version using an array takes 20 secs (using my own array-specialized ForAll method instead of Enumerable.All takes 17 secs).

EDIT: After seeing Lee's answer, I tried List.forall and it's even faster than array (~5 secs).