Project Euler - Problem #5

I was not entirely happy with the solution for this, primarily because of the time it takes to find the answer.  If I had more insight into the mathematical relationships between factor, the calculation would have been streamlined.


Description

• 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
• What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Overview

1. for every number from 1 to some maximum (or until)
2. check to see if any divisior from 1 to 20 has remainder

Solution


let remainders div num =
    let divisors = [|1..div|]
    let rem = divisors |> Array.map (fun d -> System.Math.DivRem(num,d))
    rem


let isEvenlyDivisble div num = 
    let resultPartial  = remainders div num
    let resultRemainder = resultPartial |> Array.map (fun x -> snd(x))
    let sum = Array.sum resultRemainder
    if sum = 0 then
        true
    else
        false


let smallestWithNoRemainder div = 
    let mutable state = false
    let mutable i = 1
    while state = false do
        state <- isEvenlyDivisble div (i)
        i <- i+1
    i-1
    
Unit Tests


//verify individual functions
let unitTest2_0 = isEvenlyDivisble 10 2520
let unitTest2_1 = isEvenlyDivisble 10 2521
let unitTest2_2 = isEvenlyDivisble 10 2519
let unitTest2_3 = isEvenlyDivisble 3 6


//step up to calculating 20, by verifyng smaller steps
let unitTest3_1 = smallestWithNoRemainder 1
let unitTest3_2 = smallestWithNoRemainder 2
let unitTest3_3 = smallestWithNoRemainder 3
let unitTest3_4 = smallestWithNoRemainder 4
let unitTest3_5 = smallestWithNoRemainder 10
let unitTest3_6 = smallestWithNoRemainder 11
let unitTest3_7 = smallestWithNoRemainder 12
let unitTest3_8 = smallestWithNoRemainder 13
let unitTest3_9 = smallestWithNoRemainder 14
let unitTest3_10 = smallestWithNoRemainder 20