Find sum of even numbers in Fibonacchi seq

This is the problem: https://projecteuler.net/problem=2

This is my (probably absolutely horrible) way of doing this in python:


def fib(i):
    if i == 0:
        return 0
    elif i == 1:
        return 1
    else:
        return fib(i-1) + fib(i-2)

array0 = []
array1 = []

for i in range(0, 50):
    array0.append(fib(i))
 
for i in array0:
    if i % 2 == 0:
        print '%d even' % i
        array1.append(i)
    else:
        print '%d odd' % i

print sum(array1)

I have only tested this with the first 40 numbers in the Fibonacci sequence, I cannot seem to get it to interpret anything much bigger. I've only left it on for like 10 minutes though when trying to find the first 100 and came back and it was still interpreting it. I think it froze but I can't tell.

How the HELL does this work btw:

return fib(i-1) + fib(i-2)

This shit is just a complete mindfuck to me.

Woops, that was supposed to be:

for i in range(0, 34):

you're recalculating everything everytime you call fibs
so yeah it is slow..

return fib(i-1) + fib(i-2) is a recursive function call... you can use a much simpler recursion, and it'll be way faster =D

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

>>3

I get that it's recursively calling the function inside itself.

But I seriously cannot understand truly how it's working though. I know what the fibonacci sequence is, but I've stared at that one piece of code for like an hour trying to wrap my head around how it works.

Maybe if I has an easier to understand example of recursively calling a function inside itself using something else other than a fibonachi sequence algorithm.


a = 0;
b = 1;
c = 0;
d = 0;

for(iter=1:count/3)
  a=c+b;
  b=c+a;
  c=a+b;
  d=d+c;
  endfor;

fprintf("%i", d);

>>6

I must be brain damaged. I just can't keep this stored in my head long enough to get through processing it in my mind and figuring it out.

a,b & c are just calculating fibs, every third step is even (variable c), so sum them up (d=d+c)

no need to worry about exponential function calls...

Jesus Christ OP, this is literally the worst possible way to solve this problem.

If you already know fib(x), then you're just one step away from calculating fib(x+1), but you're calculating it from the beginning every single time.

Then you're storing ALL the values in a list, including the odd numbered values, then you're storing all the even number values in a different list. Why don't you just keep a running total?

Here's a tip: you don't need the fibonacci function. You only need two variables, a and b. Let a be the first fibonacci value and b be the next. Initialize them at a = 1 and b = 2. Let c be the total initialized at c = 0. Now use a and b to calculate the next values of a and b: a = 1, b = 2; a = 2, b = 3; a = 3, b = 5; a = 5, b = 8. When a is even, add it to the running total c. When a exceeds 4M, stop.

>>7
just code it up and print the variables at each iter =)
it will be like
iter 1
a=1 / b=1 / c=2 / d=2

iter 2
a=3 / b=5 / c=8 / d=10

iter 3
a=13 / b=21 / c=34 / d=44

...bit harder to do with the recursive call though, basically (from memory) the calls to fib end up looking like the fib sequence itself..

ie.
fib(10) = fib(9) + fib(8) [x1]
fib(9) = fib(8) + fib(7)  [x1]
fib(8) = fib(7) + fib(6)  [x2]
fib(7) = fib(6) + fib(5)  [x3]
fib(6) = fib(5) + fib(4)  [x5]
... fib(n) is called fib(10 - n) times

I've done it a long time ago
here's my solution

#include <stdio.h>
#include <windows.h>





int main()
{
   
    int fib1 = 1;
    int fib2 = 1;
    int fib3;
   
    int sum = 0;
   
    for (fib3=fib2+fib1; fib3 < 4000000; fib3=fib2+fib1)
    {
        if (fib3%2 == 0)
        {
            sum += fib3;
        }
        fib1 = fib2;
        fib2 = fib3;
    }      
   
   
    printf("%d\n", sum);
   
    system("pause");
   
}

What's with the arbitrary blank lines? Also

#include <windows.h>
system("pause");

Why do you people bother coming here?

>>12

u mad?

le dox

Looks like OP hasn't read his SICP :(

>>12
>le pedophile linux

>>15
but isn't that exactly how sicp tells you to code fibs? lol

btw, i didn't read sicp, and i wrote >>6 =)

Sicp Challenge!
Calculate how many times op's code would call fib(), assuming fib(100) was called once.

Sicp Challenge II !!
Every year america tells a number of fibs. In the first year, it told 1 fib. Each time it tells a new fib, it will re-tell that same fib the year after, and tell a new fib to back that fib up two years later. Also, each year it tells 1 more new fib, except leap years.
How many different fibs has america told after 200 years?

>>17
It gives it as an example of tree recursion. It goes on to say how terrible the method is, and gives an iterative example.

>>22
thank you

>>18
The complexity of recursive fib() is O(fib(n)), so fib(100) would call fib() fib(100) = 354224848179261915075 times.

>>18
>>22
>le pedophile sage

>>4
OH SHIT U CRACKED THE PATTERN

>>19
http://www.youtube.com/watch?v=4-VfAq3bcVI

>>24
yeh, it was only a modulo 2 pattern =)

>>4 Illuminatus