CODEWITHSUNDEEP
c++sumfibonacci
ImSahil
ImSahil

Reputation: 21

Last digit of sum of squares of Fibonacci numbers

#include <iostream>
using namespace std;

int previous_fibonacci_last_digit(unsigned long long m) {
int previous = 0, current = 1;
for (unsigned long long i = 2; i <= m; i++) {
    int tmp_previous = previous;
    previous = current;
    current = ((tmp_previous % 10) + (current % 10)) % 10;

   return current;
}

int last_digit(unsigned long long n) {
     int lastDigit = ( previous_fibonacci_last_digit(n) * ( ( previous_fibonacci_last_digit(n) + previous_fibonacci_last_digit(n - 1) ) % 10 ) ) % 10 ; // found the last digit of the sum of squares of n fib numbers

     return lastDigit;
  }

To find the last digit of sum of squares of n fib numbers I found that the sum can be written as F(n) {F(n) + F(n-1)} and I was implementing it for large values. When I used long long int my program crashed at n = 260548 so I changed it to unsigned long long int and now my program is crashing at n = 519265.

I tried debugging it by seeing if the loop goes till 500000 by adding a cout in the previous_Fibonacci_last_digit() function but I found that the loop is not even running till 500000 when n = 519265. I am just storing the last digit of each Fibonacci numbers so I don't think that there is any integer overflow in it.

Edit - Instead of using arrays, now after using variables to store the last digit the program works fine but using it for n = 1234567890, it takes alot of time.

Upvotes: 2

Views: 3948

Answers (4)

abhiroop mukherjee
abhiroop mukherjee

Reputation: 69

For this, you need to devise a formula. if you see the sum of sqaure in a series - 0,1,2(1+1),6(1+1+4),15(6+9),40,104,273,714,...

you will notice, that the last digit of any number element in the series will be in the following formula - Fn = (((Fn-1 + Fn-2)x2) - Fn-3)%10

for example - to find the last digit of F7 - ((104 + 40)x2) - 15=273%10 = 3

Here's the code:-

static int fiboSumOfSquaresLastDigit(int num)
        {
            int[] fibo = new int[num+1]; 
            fibo[0]=0; 
            fibo[1]=1; 
            fibo[2]=2;

            for(int i=3; i<=num; i++)
            {
                fibo[i]= (((fibo[i-1]+fibo[i-2])*2) - fibo[i-3])%10; 
            }
            return fibo[num];
        }

Upvotes: 0

Harshit Nigam
Harshit Nigam

Reputation: 244

    #include <bits/stdc++.h>

using namespace std;

int fib(long long num ){
    int pre=0,cur=1;
    num = num %60;
    if(num==0){
        return 0;}
    else if (num == 1){
        return 1;
    }
    else{
    for (int i =2; i<=num; i++){
        int temp = (pre+cur)%60;
        pre = cur;
        cur = temp;
        // cout<<pre<<"\n"<<cur<<"\n";
    }
    }
    
    return(cur); 
}

int main() {
    long long n = 0;
    cin >> n;
    int a = fib(n);
    int b = fib(n+1);
    
    cout<<(a*b)%10;
    
    
}

the sum of squares of up to any Fibonacci numbers can be calculated without explicitly adding up the squares.

As you can see

F1^2+..Fn^2 = Fn*Fn+1

Now to calculate the last digit of Fn and Fn+1, we can apply the Pisano period method

the last digit can be calculated by %10 and the Pisano period for mod 10 is 60. so, % 60 is used in the code directly...

Upvotes: 4

Kubra Altun
Kubra Altun

Reputation: 405

I would like to share my solution as well, which is very similar to the two of the solutions above. On the other hand, I will try to provide explaining as much as possible and I do one step differently, and depending on that difference my code got through all the tests.

The first equation to consider is that: F_N * F_N+1

Hence instead of calculating a Fibonacci squares in each step (which take too long as can be predicted) we only need nth and (n+1)th Fibonacci values.

But also, it is unpractical to calculate the values that are higher than the Pisano period (which is simply the period that the remainder value repeats itself). Since we are only looking for the last digit, we can consider the problem as the module 10 of the calculated square sum of the Fibonacci values. And since Pisano period for modulo 10 is 60, we can use this value here.

That is why, for any given input number of n, if we take the modulo 60 of n and calculate the sum of the squares, we would decrease the computational time effectively.

And at the end, by taking the modulo 10 of the calculated value, we can return the last digit. Here is the code;

def last_digit_of_the_sum_of_squares_of_fibonacci_numbers(n):
   

    if n <= 1: #Check if the input value is too small
        return n

    n = n%60 #If not, take the mod60 of the input


    pre = 0 #First value of the Fibonacci series
    curr = 1 #Second value of the Fibonacci series
    for i in range(2, n+2): #Iterate until n+2, since we are looking for F_N + F_{N+1}
        pre, curr = curr, (pre+curr) #Calculate the current Fibonacci value

    return (pre*curr)%10 #return the mod10

Upvotes: 1

Sandeep V
Sandeep V

Reputation: 11

Code in Python

def pisano_num_mod10(n):
   previous, current = 0, 1
   n=n%60 #num mod 10 gives 60 repeatations in Pisano Series.. Check Wikipedia by searching for Pisano Series to get more Info
   if (n == 0): 
       return 0
   elif (n == 1): 
       return 1
   else:
       for _ in range(2,n+1):
           previous, current= current, (previous + current)%60
       return current
if __name__ == '__main__':
    n = int(input())
    print(pisano_num_mod10(n)*pisano_num_mod10(n+1)%10)

Output:

if n=7 
pisano_num_mod10(n) returns 13
pisano_num_mod10(n+1) returns 21
It Prints 13*21%10=3

Upvotes: 1

Related Questions