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

You can use the comment system below or send my an email

comments powered by Disqus



Last Tweets

A word from our sponsor