GCD and Fibonacci Numbers - GeeksforGeeks
The first few Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….
Note that 0 is considered as 0'th Fibonacci Number.
Read full article from GCD and Fibonacci Numbers - GeeksforGeeks
You are given two positive numbers M and N. The task is to print greatest common divisor of M’th and N’th Fibonacci Numbers.
Note that 0 is considered as 0'th Fibonacci Number.
GCD(Fib(M), Fib(N)) = Fib(GCD(M, N)) The above property holds because Fibonacci Numbers follow Divisibility Sequence, i.e., if M divides N, then Fib(M) also divides N. For example, Fib(3) = 2 and every third third Fibonacci Number is even. Source : Wiki
static final int MAX = 1000 ; static int [] f; gcdOfFibonacci() // Constructor { // Create an array for memoization f = new int [MAX]; } // Returns n'th Fibonacci number using table f[]. // Refer method 6 of below post for details. private static int fib( int n) { // Base cases if (n == 0 ) return 0 ; if (n == 1 || n == 2 ) return (f[n] = 1 ); // If fib(n) is already computed if (f[n]!= 0 ) return f[n]; int k = ((n & 1 )== 1 )? (n+ 1 )/ 2 : n/ 2 ; // Applying recursive formula [Note value n&1 is 1 // if n is odd, else 0. f[n] = ((n & 1 )== 1 )? (fib(k)*fib(k) + fib(k- 1 )*fib(k- 1 )) : ( 2 *fib(k- 1 ) + fib(k))*fib(k); return f[n]; } // Function to return gcd of a and b private static int gcd( int M, int N) { if (M == 0 ) return N; return gcd(N%M, M); } // This method returns GCD of Fib(M) and Fib(N) static int findGCDofFibMFibN( int M, int N) { return fib(gcd(M, N)); } |