It's that time again. ;)

Question five reads:

`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?`

And here are my solutions (which I hope are correct this time).

Haskell:

module Main where import Data.List then Nothing else Just(x,x - 1)) 20) -- solved this by the help on this URL: -- (http)basildoncoder.com/blog/2008/06/10/project-euler-problem-5/ -- by increaing the loop from 2 to 2520, problem solves in seconds

As a quick note, yes I know that I could do this much quicker and cleaner with a list comprehension. I decided to use unfoldr because I wanted the experience of working with it. If it wasn't for this little desire my answer would have looked a lot more like my Python answer.

Python:

#!/usr/bin/python def div_11_to_20(divided): return all([not bool(divided % x) for x in xrange(11,20+1)]) if __name__ == "__main__": count = 2520 while div_11_to_20(count) == False: count += 2520 print "%s" % count

And finally my Perl solution:

#!/usr/bin/perl sub divide_11_to_20 { my ( $divided ) = @_; foreach (11..20) { } } my $main_count = 2520; while ( !divide_11_to_20($main_count) ) { $main_count += 2520; }

**Run Times:**

Haskell: 0m1.302s

Python: 0m0.769s

Perl: 0m0.223s

**Observations:**

It doesn't surprise me that the Perl solution ends up being the fastest on these run times. I say this because per iteration the Perl solutions has less calculations. Both the Haskell and Python solutions perform 10 divisions per iteration, where as the Perl solution only performs 10 divisions when the correct number is is being divided. Its one of those things where the difference is very small, but will become larger as the number of iterations increases.

## R Version

executes in about 2 seconds

isDivisible <- function(x)

{

for(i in 2:20)

{

if(x%%i==0){next}

else return(F);

}

return(T);

}

i <- 2520

> while(i < y){if(isDivisible(i)) {print(i); break}; i <- i+2520; if(i%%1000000==0)

## R version - updated

this tweak makes it subsecond execution ...

isDivisible <- function(x)

{

for(i in 11:20)

{

if(x%%i==0){next}

else return(F);

}

return(T);

}

## Very optimized code in Java

This program can find the lowest number divisible from 1 - n. You can set the limit to n. n can be any number you desire.

Source : http://www.mycoding.net/2011/03/java-program-to-find-the-smallest-number-divisible-by-each-of-the-numbers-1-to-20/

P.S The captcha of this website is very tough!

## Solution

my python code:

def gcd(a, b):

if b > a:

return gcd(b, a)

if b == 0:

return a

else:

return gcd(b, a % b)

def lcm(a, b):

return b * a / gcd(a, b)

s = 1

for i in range(1, 11):

s = lcm(i, s)

print s

## An alternative python solution focused on performance

I had interestingly attempted the same problem some time back (documented here at : http://codeblog.dhananjaynene.com/2010/01/least-common-multiple-what-is-the-smallest-number-that-is-evenly-divisible-by-all-of-the-numbers-from-1-to-20/ )

My solution though much longer, completes the task in about 2 seconds for a number set of 2 to 1 million

## Two less characters in the Python solution: much faster

#!/usr/bin/python

def div_11_to_20(divided):

return all(not bool(divided % x) for x in xrange(11,20+1))

if __name__ == "__main__":

count = 2520

while div_11_to_20(count) == False:

count += 2520

print "%s" % count

As you observed, it is not useful to do all the divisions, use a generator expressions instead of a list comprehension.

## More perl

Your 'divide 11 to 20' routine is expressible much more compactly using List::MoreUtils::all:

## Python version

Fast enough to be instant for input values into the thousands.

## Here Jeremiah, Thanks for

Here Jeremiah,

Thanks for sharing your solution. It looks good, and runs much faster than mine ;). One quick question, if your using "//" for your division, doesn't abs() become unnecessary?

## Python alternative

This runs in 94 us on my machine

## Hey Anon, First time I looked

Hey Anon,

First time I looked at your code I wondered if it would work. But it does, and its quite fast too. (Although Jeremiah's submission does run faster on my machine. Probably something to do with being run in Python3.) I've never seen Python code like this before, so I think it's going to take me a while to turn it to plain English, well Python English anyway.

Thanks for sharing your solution and for expanding my Python knowledge.

## Mine is actually finding the

Mine is actually finding the lcm, just in a weird way. It is finding the minimum list of prime numbers that contains the prime factors of all of the numbers between 1 and 20. If I had realized it at the time, I probably would have done something saner like the other commenters suggested. This runs about an order of magintude faster for me than my previous weird implementation:

## perl alternative

Thanks to Acme::Tools

## WOW as well niceperl! Thanks

WOW as well niceperl! Thanks for sharing Acme::Tools. I'll have to use it in the future.

## How about: result = foldl lcm

How about:

## You dont need to go from 1 to

You dont need to go from 1 to 20, as everything from 1 to 10 is covered by items 11 to 20.

`foldr lcm [11..20]`

## Pretty much the same in Racket

(apply lcm (build-list 21 add1))

.4 seconds on an old laptop

## WOW, that is nice! And thanks

WOW, that is nice! And thanks for showing me lcm. I didn't know it existed.