CODEWITHSUNDEEP
haskell
fedvasu
fedvasu

Reputation: 1252

Project Euler: A (much) better way to solve problem #5?

You probably know about project Euler question 5: get the smallest number divisble by all numbers 1 to 20.

The logic I applied was "start with the first number greater than the largest of the list(20) and also divisible by it which is 40" and stepsize of 20 (largest number)

I did this using list comprehension but it's pretty lame.

pe5 = head    [x|x<-[40,60..],x`mod`3==0,x`mod`4==0,x`mod`6==0,x`mod`7==0,x`mod`8==0,x`mod`9==0,x`mod`11==0,x`mod`12==0,x`mod`13==0,x`mod`14==0,x`mod`15==0,x`mod`16==0,x`mod`17==0,x`mod`18==0,x`mod`19==0]

Can we do this better perhaps using zipWith and filter maybe?

Just to clarify, this is not a homework assignment. I'm doing this to wrap my brain around Haskell. (So far I'm losing!)

:Thanx all

I think this is a saner way (there may be thousand more better ways but this would suffice) to do it

listlcm'::(Integral a)=> [a] -> a
listlcm' [x] = x
listlcm' (x:xs) = lcm x (listlcm' xs)

Upvotes: 4

Views: 1236

Answers (4)

hammar
hammar

Reputation: 139930

Since the spoiler has already been posted, I thought I'd explain how it works.

The smallest number divisible by two numbers is also known as the least common multiple of those numbers. There is a function for calculating this in the Prelude.

λ> lcm 10 12
60

Now, to extend this to multiple numbers we exploit the following property

lcm(a1, ... an) = lcm(lcm(a1, ... an-1), an)

In Haskell, f(f(... f(a1, a2), ...), an) can be written foldl1 f [a1, a2, ... an], so we can solve the problem with this simple one-liner:

λ> foldl1 lcm [1..20]
232792560

This finds the solution in a fraction of a second.

Upvotes: 6

Jay Adkisson
Jay Adkisson

Reputation: 461

In this particular case, you can get it for free using foldl and lcm:

euler = foldl lcm 2 [3..20]

This gives me 232792560 instantaneously.

Upvotes: 12

hmakholm left over Monica
hmakholm left over Monica

Reputation: 23342

Yes, you can do much better. For starters, rewrite to something like

head [x | x<-[40,60..], all (\y -> x`mod`y == 0) [2..20] ]

But what you really need here is not slicker Haskell, but a smarter algorithm. Hint: use the Fundamental Theorem of Arithmetic. Your Haskell solution would then start with the standard sieve-of-Eratosthenes example.

Upvotes: 3

ckwang
ckwang

Reputation: 39

Since this is a exercise in learning Haskell, I will only point out that there is a more efficient way to solve this problem mathematically but I will let you figure that out on your own. Instead, let's solve the problem in Haskell using your logic.

I simplified it a little bit:

head [x | x <- [20,40..], length( filter ( \y -> x `mod` y /= 0) [1..20]) == 0]

This creates a filter on the divisors list, and when its length is 0, it means all the divisors divide our x, so that must be our number. This reduces some of the clutter you had in your example. Note that this method is VERY slow; can you think of a better mathematical way to tackle this? Start looking at prime factorizations...

Upvotes: 0

Related Questions