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.