A problem on GCD

Question

I want to calculate $f(n)$ where $f(n)$ is given by

$$f(n) = \sum_{i=1}^n \dfrac{n}{gcd(n,i)}$$

and $2\leq n\leq 10^{12}$. Can someone tell me the fastest algorithm to calculate this.

thanks

Answer 1

For a given possible value $d$ for $gcd(n,i)$, then we have the number of possible $i$ is $\phi(\frac{n}{d})$. Hence the sum can be rewritten as $\sum\limits_{d|n}\phi(\frac{n}{d})\frac{n}{d}=\sum\limits_{d|n}\phi(d)d$

Hence assuming you factor $n$ into primes somehow, what you can do is this:

Enumerate through all factors. If $n=\prod p_{i}^{a_{i}}$ then each factor have the form $d=\prod p_{i}^{e_{i}}$ for some $0\leq e_{i}\leq a_{i}$

For each possible factor $d=\prod p_{i}^{e_{i}}$ (where all exponent are nonzero-unlike the previous line) you can calculate $\phi(d)d=\prod (p_{i}-1)p_{i}^{2e_{i}-1}$

Of course, the hard part is going to be the factoring. I'm not sure how to do that quick. It might, in the end, be slower than brute force.