Sum of GCD of all possible sequences | Pyhton3 implementation of the above approach ; A recursive function that generates all the sequence and find GCD ; If we reach the sequence of length N g is the GCD of the sequence ; Initialise answer to 0 ; Placing all possible values at this position and recursively find the GCD of the sequence ; Take GCD of GCD calculated uptill now i . e . g with current element ; Take modulo to avoid overflow ; Return the final answer ; Function that finds the sum of GCD of all the subsequence of N length ; Recursive function that generates the sequence and return the GCD ; Driver code ; Function Call
MOD = 1e9 + 7 NEW_LINE def gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT else : NEW_LINE INDENT return gcd ( b , a % b ) NEW_LINE DEDENT DEDENT def calculate ( pos , g , n , k ) : NEW_LINE INDENT if ( pos == n ) : NEW_LINE INDENT return g NEW_LINE DEDENT answer = 0 NEW_LINE for i in range ( 1 , k + 1 ) : NEW_LINE INDENT answer = ( answer % MOD + calculate ( pos + 1 , gcd ( g , i ) , n , k ) % MOD ) NEW_LINE answer %= MOD NEW_LINE DEDENT return answer NEW_LINE DEDENT def sumofGCD ( n , k ) : NEW_LINE INDENT return calculate ( 0 , 0 , n , k ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 3 NEW_LINE K = 2 NEW_LINE print ( sumofGCD ( N , K ) ) NEW_LINE DEDENT