TheAlgorithms-Python

1
"""
2
Project Euler Problem 2: https://projecteuler.net/problem=2
3

4
Even Fibonacci Numbers
5

6
Each new term in the Fibonacci sequence is generated by adding the previous
7
two terms. By starting with 1 and 2, the first 10 terms will be:
8

9
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
10

11
By considering the terms in the Fibonacci sequence whose values do not exceed
12
four million, find the sum of the even-valued terms.
13

14
References:
15
    - https://en.wikipedia.org/wiki/Fibonacci_number
16
"""
17

18
import math
19
from decimal import Decimal, getcontext
20

21

22
def solution(n: int = 4000000) -> int:
23
    """
24
    Returns the sum of all even fibonacci sequence elements that are lower
25
    or equal to n.
26

27
    >>> solution(10)
28
    10
29
    >>> solution(15)
30
    10
31
    >>> solution(2)
32
    2
33
    >>> solution(1)
34
    0
35
    >>> solution(34)
36
    44
37
    >>> solution(3.4)
38
    2
39
    >>> solution(0)
40
    Traceback (most recent call last):
41
        ...
42
    ValueError: Parameter n must be greater than or equal to one.
43
    >>> solution(-17)
44
    Traceback (most recent call last):
45
        ...
46
    ValueError: Parameter n must be greater than or equal to one.
47
    >>> solution([])
48
    Traceback (most recent call last):
49
        ...
50
    TypeError: Parameter n must be int or castable to int.
51
    >>> solution("asd")
52
    Traceback (most recent call last):
53
        ...
54
    TypeError: Parameter n must be int or castable to int.
55
    """
56

57
    try:
58
        n = int(n)
59
    except (TypeError, ValueError):
60
        raise TypeError("Parameter n must be int or castable to int.")
61
    if n <= 0:
62
        raise ValueError("Parameter n must be greater than or equal to one.")
63
    getcontext().prec = 100
64
    phi = (Decimal(5) ** Decimal(0.5) + 1) / Decimal(2)
65

66
    index = (math.floor(math.log(n * (phi + 2), phi) - 1) // 3) * 3 + 2
67
    num = Decimal(round(phi ** Decimal(index + 1))) / (phi + 2)
68
    total = num // 2
69
    return int(total)
70

71

72
if __name__ == "__main__":
73
    print(f"{solution() = }")
74