Tuesday, May 18, 2010

Problem 21: Evaluate the sum of all the amicable numbers under 10000.

First, using our fast factorize function, we implement the well-known sigma-divisor function and it’s proper companion.

let sigma n =
    factorize n
    |> Seq.groupBy id
    |> Seq.map (fun (f,s) -> (f, Seq.length s))
    |> Seq.map (fun (p,e) -> (pown p (e+1) - 1)/(p-1))
    |> Seq.fold (*) 1
    
let psigma n = sigma n - n

Then the solution is straight forward, solution (a) recursively builds a list of amicable pairs, while solution (b) uses a filter with a sequence expression.  Notice the small optimizations skipping primes.

let problem21a =
    let rec build a alist =
        match (a,psigma a) with
        | (a,b) when a <> 1 && a <> b && (psigma b) = a -> build (a+1) (a::alist)
        | (9999,_) -> alist
        | _ -> build (a+1) alist
    (build 4 []) |> List.sum
    
let problem21b =
    let isAmicable a = 
        let b = psigma a
        a <> 1 && a <> b && (psigma b) = a    
    {4..9999} |> Seq.filter isAmicable |> Seq.sum

No comments:

Post a Comment