Sum of GCD of all possible sequences | Javascript 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
var MOD = 1000000007 ; function calculate ( pos , g , n , k ) { if ( pos == n ) { return g ; } var answer = 0 ; for ( var i = 1 ; i <= k ; i ++ ) { answer = ( answer % MOD + calculate ( pos + 1 , __gcd ( g , i ) , n , k ) % MOD ) ; answer %= MOD ; } return answer ; } function __gcd ( a , b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } function sumofGCD ( n , k ) { return calculate ( 0 , 0 , n , k ) ; } var N = 3 , K = 2 ; document . write ( sumofGCD ( N , K ) ) ;