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⩽105
  • 10⩽N⩽4 x 105

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.

EFn represents 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)