Project Euler

To solve problem #23 I apply simple brute force and we get to play a little with F# sets. Find all abundant numbers below the given upper limit. Create a set of all sums of these numbers (with a small optimization where avoid computing both a+b and b+a). Then we make a set difference and sums the remaining elements.


let n = seq { 1 .. 28123 }
let abundant number = (List.sumByInt (fun x->x) (Euler_utils.divisors number)) > 2*number
let abundant_numbers = List.of_seq (Seq.filter abundant n ) 

printfn "Number of abundant numbers: %d" (List.length abundant_numbers)

let all_sums numbers = [ for i in numbers do
                             for j in (Seq.filter (fun ji -> ji >= i ) numbers) do 
                               yield i+j ] 
let all_numbers = Set.of_array [| 1..28123 |]                               
let sums = Set.of_seq (all_sums abundant_numbers)
let not_in_sum = Set.diff all_numbers sums

printfn "Sum of remaining %d" (Set.fold (+) not_in_sum 0)

The Euler_utils.divisors function computes all divisors including 1 and the number itself. Thus I compare with the number doubled in order to detect an abundant number.