CODEWITHSUNDEEP
pythonrangefibonacci
Electrolite
Electrolite

Reputation: 179

How to determine the range to calculate the last digit of the sum of Fibonacci numbers using Pisano Period?

I already solved this problem. If I understood correctly the logic is the following: since we need the last digit of a sum of Fibonacci numbers we can use:

𝐹n mod 10 == (𝐹n % Pisano 10) mod 10

My issue is with the range of the sum. I don't know how to find it. Since Pisano 10 = 60, the last digits repeat with a period of 60 so I don't need to calculate the Fibonacci values from 0 to N but I don't know how to determine this range.

I found solutions for this problem but I never understood how they found their range. For example:

Original here

def sum_fib_last(n):
    if(n <= 1):
        return n

    previous = 0
    current  = 1

    rem = n % 60 #60 is Pisano period of 10

    for i in range(2, rem + 3): 
        
        previous, current = current, (previous + current) % 60
  
    return(current-1) % 10

I don't know why the range is from (2 to rem+3) and why we return the Fibo value minus 1. Similar solution

This solution uses a different range:

def last_digit(n):
    a, b = 0, 1
    for i in range((n + 2) % 60):
        a, b = b, (a + b) % 10
    return 9 if a == 0 else a - 1

I need help to understand how these ranges where determined, I don't understand the logic behind them.

Upvotes: 0

Views: 52

Answers (1)

Frank Yellin
Frank Yellin

Reputation: 11297

They should have been a little bit clearer. The sum of the first n Fibonacci numbers is Fib(n + 2) - 1. This is easy to prove by induction.

Upvotes: 1

Related Questions