<jupyter_start><jupyter_text>Task 2: Even Fibonacci numbers. This time we'll also start with bruteforce using non-recursive algorithm in case that python cannot optimize tail recursion. Basic implementation:<jupyter_code>firstFibonacci = 1

secondFibonacci = 1

sum_of_even_fibonacci = 0

while secondFibonacci <= 4000000:
    helper = firstFibonacci
    firstFibonacci = secondFibonacci
    secondFibonacci = firstFibonacci + helper

    if secondFibonacci % 2 == 0:
        sum_of_even_fibonacci += secondFibonacci

print(sum_of_even_fibonacci)<jupyter_output>4613732<jupyter_text>This implementation gives us O(N) speed, but there is a way to do it with ~O(logN)We can achieve it by powering the matrixes with the following identity:(F(n-2), F(n-1)) * ([0,1[1,1]]) = (F(n-1), F(N))So the implementation is something like this:<jupyter_code>def generate_fibonacci(N):
    basis_a = 1

    basis_b = 1

    basis_c = 1

    basis_d = 0

    rc = 0

    rd = 1

    while N != 0:
        if N & 1:
            tc = rc
            rc = rc * basis_a + rd * basis_c
            rd = tc * basis_b + rd * basis_d

        ta = basis_a
        tb = basis_b
        tc = basis_c

        basis_a = basis_a * basis_a + basis_b * basis_c
        basis_b = ta * basis_b + basis_b * basis_d
        basis_c = basis_c * ta + basis_d * basis_c
        basis_d = tc * tb + basis_d * basis_d

        N >>= 1
    return rc

total_sum = 0

for i in range(0, 100):
    fib = generate_fibonacci(i)
    if fib <= 4000000 and fib % 2 == 0:
        total_sum += fib

print(total_sum)<jupyter_output>4613732
{'fraction_non_alphanumeric': 0.08580441640378549, 'fraction_numerical': 0.03596214511041009, 'mean_word_length': 2.758293838862559, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '280453', 'license': 'Unlicense', 'n_tokens_mistral': 633, 'n_tokens_neox': 565, 'n_words': 164, 'path': 'python/Problem2.ipynb', 'repo_name': 'ditekunov/ProjectEuler-research', 'size': '1585'}