DEV Community

Cover image for Project Euler #2: Even Fibonacci number
Kunal Kamble
Kunal Kamble

Posted on

Project Euler #2: Even Fibonacci number

Problem statement (In Short):

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,... 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed NN , find the sum of the even-valued terms. For ProjectEuler problem statement NN is four million ( 41064*10^6 ) and for HackerRank NN can be as much as 410164*10^{16} .

Links: Project Euler, HackerRank


I planned to first generate the Fibonacci sequence and then do the summation. Afterward, reiterate the algorithm to make it faster and better.

Generating the Fibonacci numbers:

Fibonacci numbers is a sequence where nth number is addition of previous 2 numbers.

f(n)=f(n1)+f(n2) f(n) = f(n-1) + f(n-2)

Here first 2 numbers are 1 and 2 respectively. Please note that the first two numbers can vary from sequence to sequence. For this problem we can calculate the Fibonacci number at NthN^{th} index by following recursive code:
def rec_fibonacci_number(at: int) -> int:
    if at == 0:
        return 1
    if at == 1:
        return 2
    return rec_fibonacci_number(at - 1) + rec_fibonacci_number(at - 2)
Enter fullscreen mode Exit fullscreen mode

However here we want the sequence, so we have to call the recursive method repeatedly (e.g. [rec_fibonacci_number(at=0), rec_fibonacci_number(at=0), ...]). As an optimization, we can modify the recursive function to populate/cache the Fibonacci series as it goes. Now we have to call this function with the index of the maximum Fibonacci number less than NN . But we don't have that index and calculating it would require generating the sequence once in some capacity. So here using an iterative algorithm should be the wisest choice.

Iterative code to generate the Fibonacci series till we reach the upper limit:

def fibonacci_numbers(till: int) -> int:
    if till <= 1:
        return []
    if till == 2:
        return [1]

    seq, nxt = [1], 2
    while nxt < till:
        seq.append(nxt)
        nxt = seq[-1] + seq[-2]

    return seq
Enter fullscreen mode Exit fullscreen mode

#1 Naive solution:

We now have a sequence till NN , next we need to calculate the sum of even Fibonacci numbers. We can just iterate and add all even numbers from the sequence.

def naive_sum_of_even_fibonacci_numbers(till: int) -> int:
    sum_of_even_nums = 0
    for num in fibonacci_numbers(till):
        if num % 2 == 0:
            sum_of_even_nums += num
    return sum_of_even_nums
Enter fullscreen mode Exit fullscreen mode

#2 Picky solution:

If we print the Fibonacci sequence we can see a pattern.

123581321345589144233377610987... \begin{array}{} 1 & \color{greenyellow}{2} & 3 & 5 & \color{greenyellow}{8} & 13 & 21 & \color{greenyellow}{34} & 55 & 89 & \color{greenyellow}{144} & 233 & 377 & \color{greenyellow}{610} & 987 & ... \end{array}

We can see that every 3rd number is an even number. To prove this we first need to know that if we add 2 odd or even numbers, addition will be even and otherwise in the remaining 2 cases addition will be odd. Please refer to Even and Odd (Parity) Properties for more information.

The first and second numbers are odd and even respectively then the third and fourth numbers will be odd with respect to the summation of the previous numbers. The fifth number will be even as the last two numbers are odd. This is a repeating sequence, so from this point on wards odd, odd, even sequence will be followed.

12358132134...oddevenoddoddevenoddoddeven... \begin{array}{cc} 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & ...\newline odd & even & \color{greenyellow}{odd} & \color{greenyellow}{odd} & \color{greenyellow}{even} & odd & odd & even & ... \end{array}

Thus now we can just add every 3rd number after 2nd (i.e. 1st index) number.

def picky_sum_of_even_fibonacci_numbers(till: int) -> int:
    fib_nums = fibonacci_numbers(till)
    return sum(fib_nums[i] for i in range(1, len(fib_nums), 3))
Enter fullscreen mode Exit fullscreen mode

#3 Fast solution:

We know that every third number is an even number in the Fibonacci sequence. The question now is can we update the Fibonacci sequence formula to just calculate the even numbers (or each 3rd number). Upon scribbling the equations myself and looking some reference over the internet I figured out the formula to calculate the next even number of the Fibonacci series (i.e. formula for even Fibonacci series).

Here are the calculations to figure out the formula:

f(n)=f(n1)+f(n2)Exapand f(n)=f(n2)+f(n3)+f(n3)+f(n4)=f(n2)+2f(n3)+f(n4)Exapand f(n2)=f(n3)+f(n4)+2f(n3)+f(n4)=3f(n3)+2f(n4)Exapand one f(n4)=3f(n3)+f(n4)+f(n5)+f(n6)Combine f(n4)+f(n5)=3f(n3)+f(n3)+f(n6)=4f(n3)+f(n6) \begin{align*} f(n) &= f(n - 1) + f(n - 2) & \Leftarrow Exapand \ f(n) \newline &= f(n - 2) + f(n - 3) + f(n - 3) + f(n - 4) \newline &= f(n - 2) + 2 * f(n - 3) + f(n - 4) & \Leftarrow Exapand \ f(n - 2) \newline &= f(n - 3) + f(n - 4) + 2 * f(n - 3) + f(n - 4) \newline &= 3 * f(n - 3) + 2 * f(n - 4) & \Leftarrow Exapand \ one \ f(n - 4) \newline &= 3 * f(n - 3) + f(n - 4) + f(n - 5) + f(n - 6) & \Leftarrow Combine \ f(n - 4) + f(n - 5) \newline &= 3 * f(n - 3) + f(n - 3) + f(n - 6) \newline &= 4 * f(n - 3) + f(n - 6) \end{align*}

We know that every third number is an even number so with above formula if f(n)f(n) is even then f(n3)f(n - 3) and f(n6)f(n - 6) will also be even. Let f(n)f(n) be the xthx^{th} even element and mark it as ef(x)ef(x) . If f(n)f(n) is ef(x)ef(x) , then f(n3)f(n - 3) is previous even number i.e. ef(x1)ef(x - 1) and f(n6)f(n - 6) is previous of ef(x1)ef(x - 1) i.e. ef(x1)ef(x - 1) . Therefore new equation for xthx^{th} even element will become:

f(n)=4f(n3)+f(n6)    ef(x) = 4 * ef(n - 1) + ef(n - 2) f(n) = 4 * f(n - 3) + f(n - 6) \implies \colorbox{greenyellow}{ef(x) = 4 * ef(n - 1) + ef(n - 2)}

Referred from Nth Even Fibonacci Number to explain the equations in easy terms.

Now code to generate a list of even Fibonacci numbers till upper limit will look something like this:

def even_fibonacci_numbers(till: int) -> int:
    if till < 2:
        return [0]

    seq, nxt = [0], 2
    while nxt < till:
        seq.append(nxt)
        nxt = 4 * seq[-1] + seq[-2]

    return seq
Enter fullscreen mode Exit fullscreen mode

Now we just need to do the addition of the sequence. The whole code should look something like this:

def even_fibonacci_numbers(till: int) -> int:
    if till < 2:
        return [0]

    seq, nxt = [0], 2
    while nxt < till:
        seq.append(nxt)
        nxt = 4 * seq[-1] + seq[-2]

    return seq


def fast_sum_of_even_fibonacci_numbers(till: int) -> int:
    return sum(even_fibonacci_numbers(till=till))
Enter fullscreen mode Exit fullscreen mode

Final optimizations:

We have a relatively fast algorithm. However, the HackerRank problem will run this algorithm to create a sequence in each test case. We can minimize this calculation by generating it only once for the maximum NN and using it for each test case.

Final HackerRank looks something like this:

def even_fibonacci_numbers(till: int) -> int:
    if till < 2:
        return [0]

    seq, nxt = [0], 2
    while nxt < till:
        seq.append(nxt)
        nxt = 4 * seq[-1] + seq[-2]

    return seq

def sum_of_even_fibonacci_numbers(till: int) -> int:
    summation = 0
    for x in evaluated_even_fibonacci_numbers:
        if x >= till:
            break
        summation += x
    return summation

t = int(input().strip()) # Number of test cases

# Store each test case (i.e. $N$) in a list.
test_cases = []
for a0 in range(t):
    test_cases.append(int(input().strip()))

# Pre-evaluate fibonacci list with maximum $N$
evaluated_even_fibonacci_numbers = even_fibonacci_numbers(max(test_cases))

# Now calculate summation
for n in test_cases:
    print(sum_of_even_fibonacci_numbers(n))
Enter fullscreen mode Exit fullscreen mode

We can make further optimization in this by caching the sum. But that's for some other day.

Thank you for reading.

Discussion (0)