Home

Project Euler: Problem 5

Submitted by Bryce on Thu, 07/29/2010 - 10:06

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.
#1Submitted by Dhananjay Nene (not verified) on Sat, 07/31/2010 - 06:52.

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

My solution though much longer, completes the task in about 2 seconds for a number set of 2 to 1 million
#2Submitted by Jean Daniel Browne (not verified) on Fri, 07/30/2010 - 15:45.

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.
#3Submitted by Paul Evans (not verified) on Fri, 07/30/2010 - 04:52.

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. }
#4Submitted by Jeremiah (not verified) on Thu, 07/29/2010 - 17:38.

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.
#5Submitted by Bryce on Thu, 07/29/2010 - 17:54.

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?
#6Submitted by Anonymous (not verified) on Thu, 07/29/2010 - 13:59.

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)
#7Submitted by Bryce on Thu, 07/29/2010 - 18:05.

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.
#8Submitted by Anonymous (not verified) on Thu, 07/29/2010 - 21:10.

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))
#9Submitted by niceperl (not verified) on Thu, 07/29/2010 - 12:29.

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
#10Submitted by Bryce on Thu, 07/29/2010 - 14:08.

WOW as well niceperl! Thanks

WOW as well niceperl! Thanks for sharing Acme::Tools. I'll have to use it in the future.
#11Submitted by Anonymous (not verified) on Thu, 07/29/2010 - 11:51.

How about: result = foldl lcm

How about:

  1. result = foldl lcm 1 [1 .. 20]
#12Submitted by OJ (not verified) on Sat, 07/31/2010 - 14:45.

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]
#13Submitted by Anonymous (not verified) on Thu, 07/29/2010 - 17:09.

Pretty much the same in Racket

(apply lcm (build-list 21 add1))

.4 seconds on an old laptop
#14Submitted by Bryce on Thu, 07/29/2010 - 14:04.

WOW, that is nice! And thanks

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

Post new comment

Google Friend Connect (leave a quick comment)
loading...
The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.
  • You can enable syntax highlighting of source code with the following tags: <geshi>, <c>, <cpp>, <drupal5>, <drupal6>, <haskell>, <java>, <javascript>, <perl>, <php>, <python>, <ruby>. The supported tag styles are: <foo>, [foo].

More information about formatting options