11
\$\begingroup\$

I'm a fairly new programmer (just started yesterday!). I decided to tackle Project Euler #2 today, as I did #1 yesterday without many problems. I came up with what seems to me to be a working solution, but I feel like I did it in an exceedingly ugly way. Could anyone suggest improvements to my code and/or logic?

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

fib = 1
fib2 = 2
temp = 0
total = 0

while temp <=4000000:
    temp = fib2
    if temp % 2 == 0:
        total += temp
    temp = fib + fib2
    fib = fib2
    fib2 = temp

print total

I just sort of used my temp variable as a holding ground for the results, and then juggled some variables around to make it do what I wanted... Seems like quite a mess. But it does result in 4613732, which seems to be correct!

\$\endgroup\$
13
\$\begingroup\$

I would use separately Fibonacci generator

def even_fib(limit):
    a, b = 0, 1
    while a < limit:
        if not a % 2:         
            yield a
        a, b = b, a + b

And sum function to calculate sum of items

print sum(even_fib(4000000))
\$\endgroup\$
  • 1
    \$\begingroup\$ +1. Aside from the use of a generator, this refactor has two improvements that bear mentioning explicitly. The first is tuple assignment to drop temp - another way to achieve the same is: a = a + b; b = a + b, but the tuple assignment logic is much more straightforward. The other one is if not a%2 is, at least arguably, better than comparing against zero. \$\endgroup\$ – lvc Mar 9 '12 at 7:41
5
\$\begingroup\$

I'm also a fellow newbie but the way I would approach it is to first create a separate function for calculating the value for a given nth term in the Fibonacci sequence. Here's my solution:

def fibonacci(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return fibonacci(n-2) + fibonacci(n-1)

total = 0
i = 1
while fibonacci(i) <= 4000000:
    if fibonacci(i) % 2 == 0:
        total += fibonacci(i)
    i += 1
print(total)
\$\endgroup\$
  • 1
    \$\begingroup\$ Very clean solution, but I will point out that the recursive solution becomes exponentially slower as n becomes large. \$\endgroup\$ – RubberDuck Aug 6 '14 at 0:09
  • \$\begingroup\$ As @ckuhn203 said, this solution is too slow man, recursion is not a good way to handle this, compared to my solution I'm in the speed of light, haha just kidding... or not... \$\endgroup\$ – matheussilvapb Aug 7 '14 at 19:17
  • \$\begingroup\$ It is massive compute since for every value of i we are recomputing fibonacci. Instead computing fibonacci(4000000) would be better in single go and computing sum \$\endgroup\$ – djinn May 15 '16 at 3:58
  • \$\begingroup\$ The problem with this answer is not that it's recursive; it's that every iteration, it recalculates the entire fibonacci sequence. A recursive solution that yields the even integers each iteration is about as fast as the generator solution submitted by @San4ez. I can't submit the code because I don't have enough rep, however for me the generator clocks at 13 s and the recursive at 16 s for 10^6 calculations. \$\endgroup\$ – JDG Dec 15 '17 at 15:14
3
\$\begingroup\$

First of all, I'd like to tell you that the fibonnaci series starts at 1 and the second number is 1, because 1+0=1, so a fibonacci series starts like this: [1, 1, 2, 3, 5, 8...]

I know you can say it's kind of cheatting but anyways: Fibonacci series follows a pattern, because to get an even number out of a sum you'll need 2 even or 2 odd numbers(3+3=6, 6 is even; 3+5=8; 2+8=10). Starting at 1 (odd) it follows this pattern: [odd, odd, even, odd, odd, even...].

Cheating or not this is my solution:

def generate_fib(max_value):
    series = [1, 1]
    while True:
        next_last = series[-1] + series[-2]
        if next_last > max_value:
            break
        series.append(next_last)
    return series

series = generate_fib(4000000)
evens = [series[x] for x in range(2, len(series), 3)]
print(sum(evens))
\$\endgroup\$
  • \$\begingroup\$ If you solve it and look at the corresponding solution pdf (note the checkmark, pdf, and person icons to the right of the Solved By column) you will see an even more optimized solution that isn't 'cheating' but rather recommended. \$\endgroup\$ – user22048 Apr 21 '14 at 18:26
  • \$\begingroup\$ Saying that the Fibonacci sequence starts at zero does not break the algorithm. It's completely reasonable to believe that it does start at zero. \$\endgroup\$ – RubberDuck Aug 6 '14 at 1:18
  • \$\begingroup\$ @ckuhn203 actually it can't start at zero because the next number is defined by the sum of the two preceding numbers, so if you start at zero you'll have [0] the second number will be the first number plus zero because you still don't have 2 numbers, and it'll become [0, 0], then the third will be 0, the forth, the fifth all of them will be equal to zero... that's why you can't start the fibonacci series at zero. \$\endgroup\$ – matheussilvapb Aug 7 '14 at 18:59
  • 1
    \$\begingroup\$ Some say that the Fibonacci Sequence is 0, 1, 1, 2, …; other say it is 1, 1, 2, …. Either way, it makes no difference if you just want to find the sum of the even entries. \$\endgroup\$ – 200_success Aug 7 '14 at 19:20
  • 1
    \$\begingroup\$ It takes two fixed consecutive entries to uniquely define a Fibonacci-type sequence. The zero-based definition just says that it starts with 0, 1, …. A silly definition of 0, 0, … would, of course, result in all zeroes. \$\endgroup\$ – 200_success Aug 7 '14 at 19:30
3
\$\begingroup\$

@San4ez gave you a good solution, I would use the Single Responsability principle and define:

def fibs(limit):
    a, b = 0, 1
    while a < limit:
        yield a
        a, b = b, a + b

print(sum(i for i in fib(4000000) if i % 2 == 0))

so that the fibs function does not check evenness

\$\endgroup\$
  • \$\begingroup\$ Please explain the downvote, what is the problem of this answer. \$\endgroup\$ – Caridorc Apr 2 '16 at 8:48
  • 1
    \$\begingroup\$ I don't know why they downvoted, but your solution takes about 50% more time to compute. Efficiency isn't everything though and separation of responsibility is important. \$\endgroup\$ – JDG Dec 15 '17 at 14:56

protected by 200_success Jul 11 '15 at 6:30

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.