## Project Euler: Problem 5

It's that time again. ;)

`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).

`module Main where import Data.List divisible_11_to_20 number = 10 == (length \$ unfoldr(\x -> if (snd \$ quotRem number x) /= 0 || x < 11  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 secondsmain :: IO ()main = print \$ until (divisible_11_to_20) (+2520) 2520`

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)  {     return 0 if (\$divided % \$_);  }   return 1;} my \$main_count = 2520;while ( !divide_11_to_20(\$main_count) ){	\$main_count += 2520;} print \$main_count;`

Run Times:
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

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/

`public class test {	public static long LCM(long a,long b)	//Function to find LCM	{	long num1=a,num2=b;	while(a!=b)	{		if(a<b)		{			a+=num1;		}		else		{			b+=num2;		}	}	return a;	}public static void main(String args[]){	long num = 1;	int limit = 20; //This is the limit,you can change it to whatever you want.	int i=2;	//Initializing i to 2	System.out.println("This program will find out the least number which is divisible by 1-20.");	while(i<limit)	//While loop executes till i reaches the limit.	{		num=LCM(num,i);	//Calling LCM function to calculate the LCM of the current'num' and 'i'		i++;	//Incrementing i	}	System.out.println("The answer is: "+num);	//Prints the final answer. }//End of main}//End of class`

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:

`use List::MoreUtils qw( all ); for(my \$x = 2520; ; \$x += 2520) {  print "\$x\n" and last if all { \$x % \$_ == 0 } 11 .. 20;}`

### Python version

`#!/usr/bin/python3 def gcd(a,b):    if b>a: return gcd(b,a)    if b == 0: return a    return gcd(b, a-b*(a//b)) def lcm(a,b):    return abs(a*b)//gcd(a,b) def maxLcm(num):    prod = 1    for i in range(1,num+1):        prod = lcm(i,prod)    return prod print(maxLcm(20))`

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

`from collections import defaultdictimport operatorfrom itertools import starmap primes = [2,3,5,7,11,13,17,19] def factor(n):    factors = defaultdict(int)    p = 0    while n > 1:        if n % primes[p] == 0:            n /= primes[p]; factors[primes[p]]+=1        else:            p+=1    return factors def gf(n):    factors = defaultdict(int)    for i in range(n):        ifact = factor(i)        for p,c in ifact.iteritems():            if factors[p] < c: factors[p] = c    return reduce(operator.mul,starmap(pow, factors.items()))  if __name__== '__main__':    print gf(20)`

### 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:

`def gcd(a,b):    # Euclid's algorithm    while b > 0:       a, b = b, a % b   return a def lcm(a,b):    return a * b / gcd(a,b) print reduce(lcm, range(1,21))`

### perl alternative

Thanks to Acme::Tools

`#!/usr/bin/perlsub gcd {   my(\$a,\$b,@r)=@_;   @r ? gcd(\$a,gcd(\$b,@r)): \$b==0 ? \$a : gcd(\$b, \$a%\$b) }sub lcm {   my(\$a,\$b,@r)=@_;   @r ? lcm(\$a,lcm(\$b,@r)) : \$a*\$b/gcd(\$a,\$b) } print lcm(1..20), "\n";#prints: 232792560`

### 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

`result = foldl lcm 1 [1 .. 20]`

### 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]`