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