## Even Fibonacci numbers

### Problem

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.

Ans:4613732

Code for above Problem

```
def compute():
ans = 0
x = 1 # Represents the current Fibonacci number being processed
y = 2 # Represents the next Fibonacci number in the sequence
while x <= 4000000:
if x % 2 == 0:
ans += x
x, y = y, x + y
return str(ans)
if __name__ == "__main__":
print(compute())
```

Programming Version of the Problem from Hackerrank.com

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 **N** , find the sum of the even-valued terms.

**Input Format**

First line contains **T** that denotes the number of test cases. This is followed by **T **lines, each containing an integer,**N** .

**Constraints**

**1⩽T⩽10**^{5}**10⩽N⩽4 x 10**^{5}

**Output Format**

Print the required answer for each test case.

**Sample Input **

```
2
10
100
```

**Sample Output **

```
10
44
```

**Explanation **

- For
**N=10**, we have**{2,8}**, sum is**10**. - For
**N=100**, we have**{2,8,34}**, sum is**44**.

A simple solution is to iterate through all prime numbers while the next number is less than or equal to given limit. For every number, check if it is even. If the number is even, add it to the result.

An efficient solution is based on the below recursive formula for even Fibonacci Numbers

Recurrence for Even Fibonacci sequence is: EFn = 4EFn-1 + EFn-2 with seed values EF0 = 0 and EF1 = 2.EFnrepresents n'th term in Even Fibonacci sequence.

Refer this more details of above formula.

**Solution:-**

```
n =int(input())
for j in range(n):
x= int(input())
z =[1, 2];
s =2
while(z[-1]+z[-2]<=x):
z.append(z[-2]+z[-1])
if(z[-1]%2 == 0):
s+=z[-1];
print(s)
```