The following link shows 10000 perfect power.
I was wondering how many numbers are there less than $n$ that are perfect power and also co-prime with $n$. i.e. $gcd(n,k) = 1$.
In general I would like get to get sum of all co-prime perfect powers that are less than.
$$S(n) = \sum_{k,\gcd(k,n)=1}^{n} (n \bmod k)$$
How do I calculate this sum efficiently for any random $n$?