Project Euler - Problem 21

Description

• Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
• If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.
• For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284.
• The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
• Evaluate the sum of all the amicable numbers under 10000.

Solution (Improved)

let DivisorsSum num = [1..num] |> List.filter (fun x -> num % x = 0 && x < num) |> List.sum

let rec matchLists num max arr =
    if num = max then
        (List.sum arr)/2
    else
        let newTest = DivisorsSum num
        let check = DivisorsSum(newTest)
        if num = check && newTest <> check then
            matchLists (num+1) max (List.append arr [newTest+check])
        else
            matchLists (num+1) max arr

let UT_matchLists_10000 = matchLists 1 10000 []

Solution (Original)

let filteredDivisors num = [1..num] |> List.filter (fun x -> num % x = 0 && x < num)

let rec factorList num max arr =
    if num = max then
        arr
    else
        let newArr = List.append arr [(num), List.sum (filteredDivisors (num))]
        factorList (num+1) max newArr

let crossProductMatch l1 l2 =
  seq { for el1 in l1 do
          for el2 in l2 do
            if el1 = el2 then yield el1, el2 }

let resultingPairs max =
    let list1 = factorList 1 max [] |> List.filter (fun x -> fst(x) <> snd(x))
    let list2 = list1 |> List.map (fun x -> (snd(x),fst(x)))
    let listMatched = Seq.toList(crossProductMatch list1 list2)
    let listFiltered = listMatched |> List.map (fun x -> fst(x)) |> List.map (fun x -> fst(x))
    List.sum listFiltered
  
let UT_resultingPairs_10000 = resultingPairs 10000