Project Euler 48

In order to keep the numbers in check we use the rule that

$$ a \equiv v (\bmod m) \Rightarrow a b \equiv v b (\bmod m) $$

This rule is implemented in the powermod function. Note, that the powermod function is not yet “tail recursive” and is therefore vulnerable to stack overflow for (very) large b.


let rec powermod a b m =
    if b = 0I then
      (a*(powermod a (b-1I) m)) % m

let sum = 
   let numbers = [1I .. 1000I]
   let res = numbers numbers 
             |> (fun (a,b) -> powermod a b 10000000000I)
             |> Seq.sum 
   res % 10000000000I
printfn "%A" sum 

System.Console.ReadLine() |> ignore