Summation of GCD of all the pairs up to N | PHP 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 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
< ? php $ MAX = 100001 ; $ phi = array_fill ( 0 , $ MAX , 0 ) ; $ result = array_fill ( 0 , $ MAX , 0 ) ; function computeTotient ( ) { global $ MAX , $ phi ; $ phi [ 1 ] = 1 ; for ( $ i = 2 ; $ i < $ MAX ; $ i ++ ) { if ( ! $ phi [ $ i ] ) { $ phi [ $ i ] = $ i - 1 ; for ( $ j = ( $ i << 1 ) ; $ j < $ MAX ; $ j += $ i ) { if ( ! $ phi [ $ j ] ) $ phi [ $ j ] = $ j ; $ phi [ $ j ] = ( $ phi [ $ j ] / $ i ) * ( $ i - 1 ) ; } } } } function sumOfGcdPairs ( ) { global $ MAX , $ phi , $ result ; computeTotient ( ) ; for ( $ i = 1 ; $ i < $ MAX ; ++ $ i ) { for ( $ j = 2 ; $ i * $ j < $ MAX ; ++ $ j ) $ result [ $ i * $ j ] += $ i * $ phi [ $ j ] ; } for ( $ i = 2 ; $ i < $ MAX ; $ i ++ ) $ result [ $ i ] += $ result [ $ i - 1 ] ; } sumOfGcdPairs ( ) ; $ N = 4 ; echo " Summation ▁ of ▁ " . $ N . " ▁ = ▁ " . $ result [ $ N ] . " STRNEWLINE " ; $ N = 12 ; echo " Summation ▁ of ▁ " . $ N . " ▁ = ▁ " . $ result [ $ N ] . " STRNEWLINE " ; $ N = 5000 ; echo " Summation ▁ of ▁ " . $ N . " ▁ = ▁ " . $ result [ $ N ] . " STRNEWLINE " ; ? >