Tribonacci Numbers | Program to print first n tribonacci numbers Matrix Multiplication function for 3 * 3 matrix ; Recursive function to raise the matrix T to the power n ; base condition . ; recursively call to square the matrix ; calculating square of the matrix T ; if n is odd multiply it one time with M ; base condition ; T [ 0 ] [ 0 ] contains the tribonacci number so return it ; Driver Code
def multiply ( T , M ) : NEW_LINE INDENT a = ( T [ 0 ] [ 0 ] * M [ 0 ] [ 0 ] + T [ 0 ] [ 1 ] * M [ 1 ] [ 0 ] + T [ 0 ] [ 2 ] * M [ 2 ] [ 0 ] ) NEW_LINE b = ( T [ 0 ] [ 0 ] * M [ 0 ] [ 1 ] + T [ 0 ] [ 1 ] * M [ 1 ] [ 1 ] + T [ 0 ] [ 2 ] * M [ 2 ] [ 1 ] ) NEW_LINE c = ( T [ 0 ] [ 0 ] * M [ 0 ] [ 2 ] + T [ 0 ] [ 1 ] * M [ 1 ] [ 2 ] + T [ 0 ] [ 2 ] * M [ 2 ] [ 2 ] ) NEW_LINE d = ( T [ 1 ] [ 0 ] * M [ 0 ] [ 0 ] + T [ 1 ] [ 1 ] * M [ 1 ] [ 0 ] + T [ 1 ] [ 2 ] * M [ 2 ] [ 0 ] ) NEW_LINE e = ( T [ 1 ] [ 0 ] * M [ 0 ] [ 1 ] + T [ 1 ] [ 1 ] * M [ 1 ] [ 1 ] + T [ 1 ] [ 2 ] * M [ 2 ] [ 1 ] ) NEW_LINE f = ( T [ 1 ] [ 0 ] * M [ 0 ] [ 2 ] + T [ 1 ] [ 1 ] * M [ 1 ] [ 2 ] + T [ 1 ] [ 2 ] * M [ 2 ] [ 2 ] ) NEW_LINE g = ( T [ 2 ] [ 0 ] * M [ 0 ] [ 0 ] + T [ 2 ] [ 1 ] * M [ 1 ] [ 0 ] + T [ 2 ] [ 2 ] * M [ 2 ] [ 0 ] ) NEW_LINE h = ( T [ 2 ] [ 0 ] * M [ 0 ] [ 1 ] + T [ 2 ] [ 1 ] * M [ 1 ] [ 1 ] + T [ 2 ] [ 2 ] * M [ 2 ] [ 1 ] ) NEW_LINE i = ( T [ 2 ] [ 0 ] * M [ 0 ] [ 2 ] + T [ 2 ] [ 1 ] * M [ 1 ] [ 2 ] + T [ 2 ] [ 2 ] * M [ 2 ] [ 2 ] ) NEW_LINE T [ 0 ] [ 0 ] = a NEW_LINE T [ 0 ] [ 1 ] = b NEW_LINE T [ 0 ] [ 2 ] = c NEW_LINE T [ 1 ] [ 0 ] = d NEW_LINE T [ 1 ] [ 1 ] = e NEW_LINE T [ 1 ] [ 2 ] = f NEW_LINE T [ 2 ] [ 0 ] = g NEW_LINE T [ 2 ] [ 1 ] = h NEW_LINE T [ 2 ] [ 2 ] = i NEW_LINE DEDENT def power ( T , n ) : NEW_LINE INDENT if ( n == 0 or n == 1 ) : NEW_LINE INDENT return ; NEW_LINE DEDENT M = [ [ 1 , 1 , 1 ] , [ 1 , 0 , 0 ] , [ 0 , 1 , 0 ] ] NEW_LINE power ( T , n // 2 ) NEW_LINE multiply ( T , T ) NEW_LINE if ( n % 2 ) : NEW_LINE INDENT multiply ( T , M ) NEW_LINE DEDENT DEDENT def tribonacci ( n ) : NEW_LINE INDENT T = [ [ 1 , 1 , 1 ] , [ 1 , 0 , 0 ] , [ 0 , 1 , 0 ] ] NEW_LINE if ( n == 0 or n == 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT else : NEW_LINE INDENT power ( T , n - 2 ) NEW_LINE DEDENT return T [ 0 ] [ 0 ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 10 NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( tribonacci ( i ) , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT