Geeks With Blogs
Mark Pearl

 

So today I tackled a Euler problem that I had originally looked into several months back when I initially started exploring F#

Problem

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

I decided on the brute force approach again. I believe that I could have worked with prime factors etc to have reached the solution a lot quicker – but haven’t had time to look properly into that approach.

Once again the unfold function played a big role – now that I understand it a bit better, it doesn’t look like as much black magic as it initially looked like. I would love to get any suggestions / examples of how other people have solved this problem using F#

open System

let res =
    (21) 
    |> Seq.unfold (fun x -> Some(x,x+1))
    |> Seq.filter (fun x ->        
        x % 11 = 0
        & x % 12 = 0
        & x % 13 = 0
        & x % 14 = 0
        & x % 15 = 0
        & x % 16 = 0
        & x % 17 = 0
        & x % 18 = 0
        & x % 19 = 0
        & x % 20 = 0
        )
    |> Seq.head 
    
printfn "Lowest LCM is %d" res
Console.ReadLine()
Posted on Friday, June 25, 2010 3:14 PM F# | Back to top


Comments on this post: F# Euler Problem 5

# re: F# Euler Problem 5
Requesting Gravatar...
let problem5 =
// least common factor
let rec lcf = function
| hd :: tl -> hd :: lcf (List.map (fun x -> if x % hd = 0 then x / hd else x) tl)
| [] -> []
[1..20] |> lcf |> List.reduce (*)
Left by Joel on Jun 25, 2010 8:52 PM

# re: F# Euler Problem 5
Requesting Gravatar...
Here is another brute force solution.

let testf n = [ 1 .. 20] |> List.forall (fun i -> n % i = 0)

// we know it must be a multiple of these primes..
Seq.initInfinite (fun i -> (i + 1)*(11*13*17*19))
|> Seq.filter testf
|> Seq.head
Left by dave on Jun 25, 2010 10:55 PM

# re: F# Euler Problem 5
Requesting Gravatar...
let rec gcd a b = if b = 0 then a else gcd b (a % b)
[1..20] |> List.reduceBack (fun a b -> (a / (gcd a b)) * b)
Left by AshleyF on Jun 29, 2010 7:18 PM

Your comment:
 (will show your gravatar)


Copyright © MarkPearl | Powered by: GeeksWithBlogs.net