Problem 23: Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Since we’ll be reusing the sigma-divisor function again, we’ll generalize it and move it to Calc.Generalize.  Along with that I have added a performance tuned cfactorize, which returns the canonical factorization of a number (e.g. cfactorizeI 24I = [(2I, 3); (3I, 1)], noting that the second component representing the exponent is always int32, while the first is generic).  Note that the apparent silliness of breaking out the numerator and denomenator in sigma is in order to force a “sane” generic type signature.

let inline cfactorize n (lp:Lp.lp<'a>) =
    if n = lp.one then []
    else
        let flist = factorize n lp
        let rec build (f::flist) count cflist =
            if flist = [] then
                (f,count+1)::cflist
            elif f = flist.Head then
                build flist (count + 1) cflist
            else 
                build flist 0 ((f,count+1)::cflist)
        build flist 0 []

let inline sigma n (lp:Lp.lp<'a>) =
    cfactorize n lp
    |> Seq.map 
        (fun (p,e) -> 
            let numer:'a = (pown p (e+1) - lp.one)
            let denom:'a = (p-lp.one)
            numer / denom)
    |> Seq.fold (*) lp.one

Now for our solutions.  This problem definitely calls for arrays and mutation, but it mixes gracefully with other functional techniques.  My first solution (b) suffered from poor performance due to the linear time Remove operations.

let problem23a =
    let isAbundant n = (psigma n) > n
    let abundants = {1..28122} |> Seq.filter isAbundant |> Seq.toArray
    let cannots = System.Collections.Generic.List({1..28122})    
    for i in 0..(abundants.Length-1) do
        for j in i..(abundants.Length-1) do
            ignore (cannots.Remove(abundants.[i] + abundants.[j]))
    cannots |> Seq.sum

I then attempted optimize by breaking out of inner iteration when the abundant sums began to exceed 28122.  But that didn’t make much a dent.  However, by removing the linear time Remove operations and instead zeroing out  elements by array index, speed was improved by 100-fold (from about a a minute to about two seconds).

let problem23b =
    let isAbundant n = (psigma n) > n
    let abundants = {1..28122} |> Seq.filter isAbundant |> Seq.toArray
    let cannots = {1..28122} |> Seq.toArray
    for i in 0..(abundants.Length-1) do
        let rec removeAbundants j =
            let can = abundants.[i] + abundants.[j]
            if can > 28122 then ()
            else
                cannots.[can-1] <- 0 
                removeAbundants (j+1)
        removeAbundants i
    cannots |> Seq.sum