Project Euler

Project Euler # 1

Project Euler #1
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Python:
Summation of a generator expressions using appropriate filter
LOC: 1
Python 3000 changed the behaviour of the range() function. In previous version, range() constructed the list in full, but in Python 3000 the range() function is an iterator and generates values one at a time. This replaces the xrange() function of previous Python releases. Thus, this expression is a generator expression that is passed sequentially to sum().

Haskell:
For Haskell I used a recursive fucntion, with an

 if...then...else...

construct
LOC: 3
Both the Python and Haskell versions evaluate values one-at-a-time. In Python this is achieved using the range() iterator inside the generator expression. In Haskell, this is a natural result of Haskell’s lazy evaluation. So while myHaskell is recursive, it avoids large memory overhead by evaluating the inner-most recursive call and passing this to the next recursive call, and returning this in turn to its calling recursive level and so on…

What is really interesting, is that the Python version is massively faster than the Haskell version! myNaturals takes approx. 3 seconds to evaluate [1..1 million], while Python can calculate [1..10 million] in the same time! It is worth mentioning that Python has a maximum recursion depth of 1000 (out of the box). Of course, this can be changed, but unlike Haskell, recursion is often not the “optimal” solution in Python, which favours generators and iterators in Python 3000.

Introduced a secondary approach in Haskell that uses a list comprehension in exactly the same way that Python does. => much faster and more elegant in one line of code. (Achieves [1..1 million] in approx. 2 seconds and [1..10 million] in approx. 10 seconds.)

There is a pattern in these answers:

[1..999] => 233168
[1..9999] => 23331668
[1..99999] => 2333316668
[1..999999] => 233333166668
[1..9999999]=> 23333331666668

I am sure there is some mathematical pattern here, that could be used to generate these values in O(1) time… If anyone can think of anything I would love to know!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s