Project Euler #23

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.

You can use the comment system below or send my an email

comments powered by Disqus



Last Tweets

A word from our sponsor