9
\$\begingroup\$

Here is my Python code for Project Euler #2:

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.

How well did I do and what improvements can I make?

sum = 0
fib = []
i = 2

fib.append(0), fib.append(1), fib.append(1)
while fib[i] < 4000000:
    i += 1
    fib.append(fib[i-1] + fib[i-2])
    if (fib[i] % 2 ==0):
        sum += fib[i]

print sum

EDIT: Thanks everyone for answering and commenting. All answers and some comments provide different suggestions which is very helpful.

\$\endgroup\$
  • \$\begingroup\$ As an aside, this would make a nice math question: you can work out a closed form formula (with 4000000 replaced with a variable) with paper and pencil with the right mathematical techniques. \$\endgroup\$ – Hurkyl Aug 31 '15 at 20:47
7
\$\begingroup\$

Your use of an array to store previous entries is convenient, but it requires a lot of memory use for values that will be thrown away and not reused. It's very simple to keep the two most recent values in simple variables, and not have the array at all.

Consider:

sum = 0
current = 1
previous = 1

while True:
    fib = current + previous
    if (fib > 4000000):
        break

    previous = current
    current = fib

    if (fib % 2 == 0):
        sum += fib

print sum

By eliminating the array you save a lot of management time, and space.

The code above contains a break condition inside the infinite loop instead of a loop condition. This is a common practice solution in Python for a do-while loop instead of a while-do loop.

\$\endgroup\$
  • 1
    \$\begingroup\$ Yes, using the break statement is key. In my opinion, it's usually best to write code in the most natural way -- e.g. "stop when you get past 4 million" -- rather than go through contortions to put the stopping condition in the while condition. \$\endgroup\$ – Hurkyl Aug 31 '15 at 3:35
7
\$\begingroup\$

It is not hard to see that the sequence follows a 2-odd-1-even pattern. So you can directly get the next even entry by jumping three positions ahead.

Based on these two simple formulas:

f[i] = f[i-1] + f[i-2] = 2*f[i-2] + f[i-3] = 3*f[i-3] + 2*f[i-4]
f[i-1] = f[i-2] + f[i-3] = 2*f[i-3] + f[i-4]

It should be obvious that the following, code, that doesn't need to explicitly check for even entries, also gets the job done:

odd = 1
even = 2
total = 0  # Using sum shadows the built-in function
while even < 4000000:
    total += even
    odd, even = 2*even + odd, 3*even + 2*odd

print total

EDIT As @Hurkyl suggest in the comments, it is even better to use the formula:

f[i] = 4*f[i-3] + f[i-6]

which cuts out all odd terms:

prev = 2
last = 8  # 1, *2*, 3, 5, *8*
total = 2
while last < 4000000:
    total += last
    last, prev = 4*last + prev, last
\$\endgroup\$
  • 2
    \$\begingroup\$ If you're going to do that, you might as well use f[i] = 4 * f[i-3] + f[i-6] to cut out the odd terms entirely. \$\endgroup\$ – Hurkyl Aug 31 '15 at 3:39
  • \$\begingroup\$ Nice! Not that hard to arrive at that expression once you know it exists, but not obvious it was even possible either. Have edited. \$\endgroup\$ – Jaime Aug 31 '15 at 4:24
4
\$\begingroup\$

In my opinion, rather than writing

fib = []
fib.append(0), fib.append(1), fib.append(1)

you should write

fib = [0, 1, 1]

If you feel it's important to write the code so as to start with an empty list and extend it, you could instead use

fib = []
fib += 0, 1, 1

or instead

fib = []
fib.extend((0, 1, 1))
\$\endgroup\$
3
\$\begingroup\$

Nice work getting the problem right. Here are a few pointers:

  1. Storing the full array of Fibonacci numbers isn't necessary. You are taking the sum "as you go" and not storing every summand in the sum. You would do well to do the same for the Fibonacci sequence itself. Just store the last two values.

  2. I think your code could be nicer if it were wrapped into a function. You could use Python's yield keyword to make your function a "generator function", a technique that works well with "state machine"-like approach of storing only the terms necessary to compute the next term instead of storing the full sequence.

  3. You used the reserved keyword sum as a variable name. That's bad; try to avoid doing that if at all possible.

I had my own solution to PE #2 lying around and in case it's interesting or useful to you here it is. (It uses yield and is wrapped into a function.)

def sum_fibonacci_modulo_n(start_1=1, start_2=2, n=2, max_num=4000000):
    sum_ = 0

    if not start_1 % n: 
        sum_ += start_1

    while start_1 < max_num:
        if not start_2 % n:
            sum_ += start_2
            yield sum_
        start_1, start_2 = start_2, start_1 + start_2 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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