## Project Euler 005 – F#

28 02 2011

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 *)

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

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 (24) is also divisible by 2, 4 (22), and 8 (23).  Restating this as a question: What is the highest power of 2 we need to concern ourselves with?  25 = 32  which is too big (bigger than 20).  24 = 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.