Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How can we find an asymptotic formula for $$\sum_{\substack{1\leq k\leq n \\ (n,k)=1}}f(k)?$$ Here $f$ is some function and $(n,k)$ is the gcd of $k$ and $n$. I am particularily interested in the case $$\sum_{\substack{1\leq k\leq n \\ (n,k)=1}}\frac{1}{k}.$$ I know about the result $$\sum_{\substack{1\le k\le n\\(n,k)=1}}k=\frac{n\varphi(n)}{2}$$ which was discussed here, but I don't know if I can use it in the case of $f(k)=1/k$.

share|cite|improve this question
I can do something in elementary number theory: let $g(k)=\sum_{0<k\le n, \gcd(k,n)=1}1/k$, we have $\sum_{d\mid n}g(n/d)/d=H_n$, where $H_n=\sum_{k=1}^n1/k$. We can apply Mobius inversion, but it seems no benefit. – Frank Science Jun 29 '12 at 10:48
You can try Dirichlet generating function: let $\tilde G(z)=\sum_{n>0}n^{-z}$, we have $\zeta(z+1)\tilde G(z)=\sum_{n>0}n^{-z}H_n$. It might be useful in analytic number theory. – Frank Science Jun 29 '12 at 10:52
up vote 3 down vote accepted

Hint: Try using the fact that $\sum_{d|n} \mu(d)$ is an indicator function for when $n=1$. This allows us to do the following for any function $f$:

$$\sum_{n\leq x}\sum_{k\leq n,\ \gcd (k,n)=1} f(k,n)=\sum_{n\leq x}\sum_{k\leq n} f(k,n) \sum_{d|k, \ d|n} \mu (d) =\sum_{d\leq x} \mu(d) \sum_{n\leq \frac{x}{d}}\sum_{k\leq n} f(dk,nk).$$

This method is very general, and works in a surprisingly large number of situations. I encourage you to try it.

Remark: Using this approach I get $$\sum_{n\leq x}\sum_{k\leq n,\ \gcd(k,n)=1} \frac{1}{k}=\frac{6x}{\pi^{2}}\log x+\left(-\frac{\zeta^{'}(2)}{\zeta(2)^2}+\frac{6\left(\gamma-1\right)}{\pi^{2}}\right)x+O\left(\log^{2}x\right).$$

Edit: I made a slight miscalculation in my remark, missing the factor of $\zeta(2)^2$ in the $\zeta^{'}(2)$ term, and have updated the asymptotic.

share|cite|improve this answer
Thanks! Just a quick question, what do you mean by $f(k,n)$ and $f(dk,nk)$? – Carolus Jun 29 '12 at 15:19
@Carolus: $f$ is any two variable function, $f:\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{R}$. (Note that 1 variable functions, such as $f(n,k)=\frac{1}{k}$ count as a subset. – Eric Naslund Jun 29 '12 at 16:59
I think you misunderstood the OP's idea. He want to find the asymptotics for $\sum_{0<k\le n,\gcd(k,n)=1}1/k$. The summation is over $k$, not both $k$ and $n$. – Frank Science Jun 29 '12 at 23:25
@Eric: I ran into some problems with a similar case. $\sum_{2\leq k\leq n,\ (k,n)=1}\frac{n}{k}$. Any thoughts? – Carolus Jul 2 '12 at 21:02
@Carolus: Frank Science makes a good point, perhaps I have misread your question. Is the summation over both variables, or just over 1 variable? – Eric Naslund Jul 2 '12 at 21:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.