Hello Let gcdsum[n] = gcd(1,1)+gcd(1,2)+gcd(1,3)+ ... +gcd(n,n) Also gcdsum[n] can be evaluated using :
gcdsum[n] = n*sum(eulerphi(d)/d) for all d | n Now to compute all gcdsum values upto n we first need to precompute all eulerphi and then use a sieve like algorithm to make a table of all gcdsum . But can any one tell me a way to compute the gcd sum values without computing phi . Since a table of eulerphi could be made without computing prime numbers, but i am unable to extend this idea. Can any one help ? Thanks ! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
