Program to find LCM of two Fibonnaci Numbers | Python 3 Program to find LCM of Fib ( a ) and Fib ( b ) ; Create an array for memoization ; Function to return the n 'th Fibonacci number using table f[]. ; Base cases ; If fib ( n ) is already computed ; Applying recursive formula Note value n & 1 is 1 if n is odd , else 0. ; Function to return gcd of a and b ; Function to return the LCM of Fib ( a ) and Fib ( a ) ; Driver code
MAX = 1000 NEW_LINE f = [ 0 ] * MAX NEW_LINE def fib ( n ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( n == 1 or n == 2 ) : NEW_LINE INDENT f [ n ] = 1 NEW_LINE return f [ n ] NEW_LINE DEDENT if ( f [ n ] ) : NEW_LINE INDENT return f [ n ] NEW_LINE DEDENT k = ( n + 1 ) // 2 if ( n & 1 ) else n // 2 NEW_LINE if ( n & 1 ) : NEW_LINE INDENT f [ n ] = ( fib ( k ) * fib ( k ) + fib ( k - 1 ) * fib ( k - 1 ) ) NEW_LINE DEDENT else : NEW_LINE INDENT f [ n ] = ( 2 * fib ( k - 1 ) + fib ( k ) ) * fib ( k ) NEW_LINE DEDENT return f [ n ] NEW_LINE DEDENT def gcd ( a , b ) : NEW_LINE INDENT if ( a == 0 ) : NEW_LINE INDENT return b NEW_LINE DEDENT return gcd ( b % a , a ) NEW_LINE DEDENT def findLCMFibonacci ( a , b ) : NEW_LINE INDENT return ( fib ( a ) * fib ( b ) ) // fib ( gcd ( a , b ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = 3 NEW_LINE b = 12 NEW_LINE print ( findLCMFibonacci ( a , b ) ) NEW_LINE DEDENT