Type overflow in project euler #5

I am trying to solve the project euler #5:

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 numbe开发者_运维百科rs from 1 to 20?

Here is my code:

open System

let rec gcd a b =
    match b with
        | x when x = 0 -> a
        | _ -> gcd b (a % b)

let lcm a b = (a * b) / (gcd a b)        
let result = Seq.fold lcm 1 [1..20]

[<EntryPoint>]
let main(args : string[]) =
    printfn "result = %d" result 
    0

It works fine with numbers [1..19], but I get the wrong result with numbers [1..20]. I was trying to find out the reason of error and find that:

$ Seq.fold lcm 1 [1..19]
232792560 // right
$ lcm 232792560 20
18044195 // wrong

It looks like the type overflow. How can I fix the error?

Use BigInt, an integer type which won't overflow. If you replace 0 with 0I (the I suffix is used for BigInt literals) in gcd, then both gcd and lcm will be infered to work with BigInts instead of ints.

The other solution is to redefine slightly the lcm function

let lcm a b = let m = b / (gcd a b) in a * m;; 

Since you multiply by slightly smaller numbers, it won't overflow. Euler problems are also about mathematics :p

In other languages, it's possible to work with 4-byte integer until it overflows, then the run-time upgrades your integer, and proceeds as planned.

I wonder if we could do the same thing in F#, to optimize performance.

You could use LanguagePrimitives.GenericZero instead of the literal 0. This way the gcd function and thus the lcm function are generic and will work with any numeric type. Here a solution using int64:

module Problem5 =
    let rec greatestCommonDivisor a b  = // Euclidean algorithm
        if b = LanguagePrimitives.GenericZero then  a 
        else greatestCommonDivisor b (a % b)
    let leastCommonMultiple a b  = (a * b) / (greatestCommonDivisor a b)
    // Take the least common multiple of all numbers from 1 to 20.
    let solution = [1L..20L] |> List.fold leastCommonMultiple 1L