Functional programming in Python Project Euler 2

Problem 2

"Even Fibonacci number"

The Fibonacci sequence terms are the sum of the previous two terms. If the first two terms are 1, 2, then the first 10 terms are:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Find the sum of even-valued terms with a sequence term value of 4 million or less.

Infinite list

It is not possible to define a list of infinite length in common programming languages. However, since functional languages have a mechanism called lazy evaluation and an infinite list can be easily created, it is a functional method to define the Fibonacci number sequence as an infinite list. Strictly speaking, you can't create an infinite list in Python, but you can use a generator to represent something close to an infinite list.

generator

A normal function returns a value with return, but a generator function returns a value with yield.

Generator function


def generate():
    n = 1
    yield n
    n += 1
    yield n
    n += 1
    yield n

Executing the generator function creates a generator object.

>>> generator = generate()
>>> for i in generator:
...     print(i)
... 
1
2
3

When called the first time, it returns a value in the first yield and breaks there. When called the second time, processing starts from the point where it was interrupted last time, returns a value in the next yield, and interrupts there. The difference from return is that yield does not leave the function even if the value is returned.

takewhile function

The itertools module provides functions for use in functional programming. This problem uses the takewhile function to retrieve only elements less than or equal to 4000000. The takewhile function creates an iterator that returns elements only while the conditions are met. Unlike the filter function, if the condition is not met even once, the subsequent elements will not be returned.

>>> from itertools import takewhile
>>> x = takewhile(lambda n: n < 10, range(100))
>>> list(x)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer example

# -*- coding: UTF-8 -*-
from itertools import takewhile

def generateFibonacci():
    '''Generator function to generate Fibonacci sequence'''
    n1, n2 = 1, 2
    while True:
        yield n1
        n1, n2 = n2, n1 + n2

#Create a Fibonacci sequence with a generator function.
fibonacci_sequence = generateFibonacci()

#Use the takewhile function to narrow down the range to elements of 4000000 or less.
fibonaccis = takewhile(lambda n: n <= 4000000, fibonacci_sequence)

#Extract only even numbers with the filter function.
even_fibonaccis = filter(lambda n: n % 2 == 0, fibonaccis)

answer = sum(even_fibonaccis)
print(answer)

Recommended Posts

Functional programming in Python Project Euler 1
Functional programming in Python Project Euler 3
Functional programming in Python Project Euler 2
[Note] Project Euler in Python (Problem 1-22)
Project Euler # 5 "Minimum Multiples" in Python
Programming in python
Project Euler # 15 "Lattice Path" in Python
Project Euler # 4 "Maximum Palindrome" in Python
Project Euler # 3 "Maximum Prime Factors" in Python
Project Euler # 11 "Maximum Product in Grid" in Python
Project Euler # 7 "1000 1st prime number" in Python
Project Euler # 16 "Sum of Powers" in Python
Project Euler # 9 "Special Pythagorean Triple" in Python
Project Euler # 14 "Longest Collatz Sequence" in Python
Try a functional programming pipe in Python
Project Euler # 2 "Even Fibonacci Numbers" in Python
Project Euler # 17 "Number of Characters" in Python
Project Euler # 1 "Multiples of 3 and 5" in Python
Python programming in Excel
Project Euler # 8 "Maximum Product in Number String" in Python
Project Euler # 10 "sum of prime numbers" in Python
Project Euler # 12 "High Divisibility Triangular Number" in Python
Project Euler # 13 "Sum of Large Numbers" in Python
Project Euler # 6 "Difference in sum of squares" in Python
Get in touch with functional programming in JavaScript or Python 3
GUI programming in Python using Appjar
Project Euler 37
Project Euler 7
Project Euler 47
Project Euler 4
Project Euler 38
Project Euler 17
Project Euler 26
Project Euler 8
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 33
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 46
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Create Python project documentation in Sphinx
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 11 "Maximum product in grid"
Project Euler 13
Project Euler 30
Project Euler 16