Project Euler 48

A solution to 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.

#light

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

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

System.Console.ReadLine() |> ignore