Problem 5

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?

Solution

(*

 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?

 

*)

 

(* I have put this list in the format of

   2^4, 3^2, 5^1 …

*)

let factorsWeCareAboutLessThan20 = [pown 2 4;pown 3 2;5;7;11;13;17;19]

 

(* multiply them all together *)

let answer = factorsWeCareAboutLessThan20

             |> List.fold(fun elem acc -> elem * acc)  1

 

printfn "%A" answer

 

Discussion

This is a pretty simple problem if you know what you’re looking for.  We want to find the least common multiple of (1,2,3..20). 

The key observation here is that anything that is divisible by 16 (2⁴) is also divisible by 2, 4 (2²), and 8 (2³).  Restating this as a question: What is the highest power of 2 we need to concern ourselves with?  2⁵ = 32  which is too big (bigger than 20).  2⁴ = 16 so that’s just right.  Rinse and repeat with other primes.

Later this week we might look at a more automated approach… if you’re lucky.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).