Skip to content

Problem 2

October 31, 2009

Here I will solve the problem 2 of the Euler project, using Haskell.

There are multiple possibilities to solve this problem. When I first tried to solve it, I used a brute force function that was very inefficient, so I shortly switched my approach.

My first solution used an infinite list of the fibonacci sequence, as you can see below:

fibs = 0 : 1 : [ x+y | (x,y) <- zip fibs (tail fibs) ]

Then, with a few tries in the interpreter, I discovered that I should only use the first 34 elements of that list, since after that the numbers are greater than 4.000.000. Therefore:

l = take 34 fibs

Finally, I just needed to build the final function:

f = foldr (+) 0 (filter even l)

After this solution, I just tried another one, using the golden ration number:

goldenRatio = 1.6180339887

Using the golden ration number, it is possible to find the even numbers of the fibonacci sequence (which appear in every 3 elements of the sequence). Therefore, we calculate the number below:

v = goldenRatio ^ 3

If we multiply each even number of the fibonacci sequence by this number, and if we round the result, we obtain the next even number of the sequence. Therefore, it is just a matter of finding the even elements of the sequence:

h r = case r > 4000000 of
False -> r : h (round ((fromInteger r)*v))
_ -> []

Finally, since the number 2 is the first even number of the fibonacci sequence, I just wrote a small function to return the answer for the problem:

g = foldr (+) 0 (h 2)

Advertisements
Leave a Comment

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

%d bloggers like this: