Summation of GCD of all the pairs up to N | Python approach of finding sum of GCD of all pairs ; phi [ i ] stores euler totient function for i result [ j ] stores result for value j ; Precomputation of phi [ ] numbers . Refer below link for details : https : goo . gl / LUqdtY ; Refer https : goo . gl / LUqdtY ; Precomputes result for all numbers till MAX ; Precompute all phi value ; Iterate throght all the divisors of i . ; Add summation of previous calculated sum ; Function to calculate sum of all the GCD pairs
MAX = 100001 NEW_LINE phi = [ 0 ] * MAX NEW_LINE result = [ 0 ] * MAX NEW_LINE def computeTotient ( ) : NEW_LINE INDENT phi [ 1 ] = 1 NEW_LINE for i in range ( 2 , MAX ) : NEW_LINE INDENT if not phi [ i ] : NEW_LINE INDENT phi [ i ] = i - 1 NEW_LINE for j in range ( i << 1 , MAX , i ) : NEW_LINE INDENT if not phi [ j ] : NEW_LINE INDENT phi [ j ] = j NEW_LINE DEDENT phi [ j ] = ( ( phi [ j ] // i ) * ( i - 1 ) ) NEW_LINE DEDENT DEDENT DEDENT DEDENT def sumOfGcdPairs ( ) : NEW_LINE INDENT computeTotient ( ) NEW_LINE for i in range ( MAX ) : NEW_LINE INDENT for j in range ( 2 , MAX ) : NEW_LINE INDENT if i * j >= MAX : NEW_LINE INDENT break NEW_LINE DEDENT result [ i * j ] += i * phi [ j ] NEW_LINE DEDENT DEDENT for i in range ( 2 , MAX ) : NEW_LINE INDENT result [ i ] += result [ i - 1 ] NEW_LINE DEDENT DEDENT sumOfGcdPairs ( ) NEW_LINE N = 4 NEW_LINE print ( " Summation ▁ of " , N , " = " , result [ N ] ) NEW_LINE N = 12 NEW_LINE print ( " Summation ▁ of " , N , " = " , result [ N ] ) NEW_LINE N = 5000 NEW_LINE print ( " Summation ▁ of " , N , " = " , result [ N ] ) NEW_LINE