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

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 (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.

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

Advertisements

Actions

Information

One response

3 03 2011
Project Euler 005 – TSQL «

[…] you remember from Monday’s solution (F#), I mentioned that 25 was too big (32 > 20) so 24 was the number we needed to use?  So how […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: