Project Euler: Problem 5

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:

  1. module Main where
  2.  
  3. import Data.List
  4.  
  5. divisible_11_to_20 number = 10 == (length $ unfoldr(\x -> if (snd $ quotRem number x) /= 0 || x < 11
  6. then Nothing
  7. else Just(x,x - 1)) 20)
  8.  
  9. -- solved this by the help on this URL:
  10. -- (http)basildoncoder.com/blog/2008/06/10/project-euler-problem-5/
  11. -- by increaing the loop from 2 to 2520, problem solves in seconds
  12. main :: IO ()
  13. 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:

  1. #!/usr/bin/python
  2.  
  3. def div_11_to_20(divided):
  4. return all([not bool(divided % x) for x in xrange(11,20+1)])
  5.  
  6. if __name__ == "__main__":
  7. count = 2520
  8. while div_11_to_20(count) == False:
  9. count += 2520
  10.  
  11. print "%s" % count

And finally my Perl solution:

  1. #!/usr/bin/perl
  2.  
  3. sub divide_11_to_20
  4. {
  5. my ( $divided ) = @_;
  6.  
  7. foreach (11..20)
  8. {
  9. return 0 if ($divided % $_);
  10. }
  11.  
  12. return 1;
  13. }
  14.  
  15. my $main_count = 2520;
  16. while ( !divide_11_to_20($main_count) )
  17. {
  18. $main_count += 2520;
  19. }
  20.  
  21. print $main_count;

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/

  1. public class test {
  2. public static long LCM(long a,long b) //Function to find LCM
  3. {
  4. long num1=a,num2=b;
  5. while(a!=b)
  6. {
  7. if(a<b)
  8. {
  9. a+=num1;
  10. }
  11. else
  12. {
  13. b+=num2;
  14. }
  15. }
  16. return a;
  17. }
  18. public static void main(String args[]){
  19. long num = 1;
  20. int limit = 20; //This is the limit,you can change it to whatever you want.
  21. int i=2; //Initializing i to 2
  22. System.out.println("This program will find out the least number which is divisible by 1-20.");
  23. while(i<limit) //While loop executes till i reaches the limit.
  24. {
  25. num=LCM(num,i); //Calling LCM function to calculate the LCM of the current'num' and 'i'
  26. i++; //Incrementing i
  27. }
  28. System.out.println("The answer is: "+num); //Prints the final answer.
  29.  
  30. }//End of main
  31. }//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:

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

Python version

  1. #!/usr/bin/python3
  2.  
  3. def gcd(a,b):
  4. if b>a: return gcd(b,a)
  5. if b == 0: return a
  6. return gcd(b, a-b*(a//b))
  7.  
  8. def lcm(a,b):
  9. return abs(a*b)//gcd(a,b)
  10.  
  11. def maxLcm(num):
  12. prod = 1
  13. for i in range(1,num+1):
  14. prod = lcm(i,prod)
  15. return prod
  16.  
  17. 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

  1. from collections import defaultdict
  2. import operator
  3. from itertools import starmap
  4.  
  5. primes = [2,3,5,7,11,13,17,19]
  6.  
  7. def factor(n):
  8. factors = defaultdict(int)
  9. p = 0
  10. while n > 1:
  11. if n % primes[p] == 0:
  12. n /= primes[p]; factors[primes[p]]+=1
  13. else:
  14. p+=1
  15. return factors
  16.  
  17. def gf(n):
  18. factors = defaultdict(int)
  19. for i in range(n):
  20. ifact = factor(i)
  21. for p,c in ifact.iteritems():
  22. if factors[p] < c: factors[p] = c
  23. return reduce(operator.mul,starmap(pow, factors.items()))
  24.  
  25. if __name__== '__main__':
  26. 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:

  1. def gcd(a,b):
  2. # Euclid's algorithm
  3. while b > 0:
  4. a, b = b, a % b
  5. return a
  6.  
  7. def lcm(a,b):
  8. return a * b / gcd(a,b)
  9.  
  10. print reduce(lcm, range(1,21))

perl alternative

Thanks to Acme::Tools

  1. #!/usr/bin/perl
  2. sub gcd {
  3. my($a,$b,@r)=@_;
  4. @r ? gcd($a,gcd($b,@r)): $b==0 ? $a : gcd($b, $a%$b)
  5. }
  6. sub lcm {
  7. my($a,$b,@r)=@_;
  8. @r ? lcm($a,lcm($b,@r)) : $a*$b/gcd($a,$b)
  9. }
  10.  
  11. print lcm(1..20), "\n";
  12. #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

How about:

  1. 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]

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.

If you made it this far down into the article, hopefully you liked it enough to share it with your friends. Thanks if you do, I appreciate it.

Bookmark and Share