Register Now
/** * @package WordPress * @subpackage Enterprise_LAMP */

Bryce Verdier: Project Euler: Problem 5

Posted on | July 29, 2010 | No Comments

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.

Category: Planet

Comments

Leave a Reply






Warning: include(/home/remarkwit/enterpriselamp.org/wp-content/themes/Enterprise_LAMP/r_sidebar.php) [function.include]: failed to open stream: No such file or directory in /home/remarkwit/enterpriselamp.org/wp-content/themes/Enterprise_LAMP/index.php on line 36

Warning: include() [function.include]: Failed opening '/home/remarkwit/enterpriselamp.org/wp-content/themes/Enterprise_LAMP/r_sidebar.php' for inclusion (include_path='.:/usr/local/lib/php:/usr/local/php5/lib/pear') in /home/remarkwit/enterpriselamp.org/wp-content/themes/Enterprise_LAMP/index.php on line 36