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

Can someone help me to evaluate the following sum. It appeared while calculating the number of elements of intersections of some sets: $$\sum_{d|n} \frac{d}{\phi(d)^2}.$$

share|cite|improve this question
It looks to be a multiplicative function, and the result for prime powers is somewhat tractable. Have you already looked at it to that extent? – hardmath Jul 7 '12 at 23:28
To extend on hardmath's finding I got indeed $f(p)=\frac{p^2-p+1}{(p-1)^2}$ (the 'distribution' obtained is very regular with a mean value of $\approx 3.39063$) – Raymond Manzoni Jul 7 '12 at 23:34

Since $\dfrac{n}{\phi(n)^2}$ is a multiplicative function, we know that $$ \varphi(n)=\sum_{d|n}\frac{d}{\phi(d)^2}\tag{1} $$ is also multiplicative. On the power of a prime, $p^j$ and $j>0$, $\phi(p^j)=p^j\frac{p-1}{p}$, so $$ \begin{align} \varphi(p^k) &=1+\sum_{j=1}^k\frac{p^2}{p^j(p-1)^2}\\ &=1+\frac{p}{(p-1)^2}\sum_{j=0}^{k-1}\frac{1}{p^j}\\ &=1+\frac{p^k-1}{p^{k-2}(p-1)^3}\tag{2} \end{align} $$ Thus, for $n$ whose prime factorization is $$ n=\prod_jp_j^{k_j}\tag{3} $$ we have $$ \varphi(n)=\prod_j\left(1+\frac{p_j^{k_j}-1}{p_j^{k_j-2}(p_j-1)^3}\right)\tag{4} $$ Estimation:

Note that for $k>0$, $$ 1+\frac1p\left(\frac{p}{p-1}\right)^2\le1+\frac{p^k-1}{p^{k-2}(p-1)^3}\lt1+\frac1p\left(\frac{p}{p-1}\right)^3\tag{5} $$ For larger primes, $(5)$ might help to approximate the term in $(4)$.

share|cite|improve this answer
+1 That's the expression I get. – hardmath Jul 8 '12 at 0:00
An equivalent for $f(p^k)$ is $1 + \frac{p^2}{(p-1)^3} (1 - p^{-k})$, which makes it clearer what the limit is as $k$ tends to $\infty$. – hardmath Jul 8 '12 at 0:18
@hardmath: thanks! I was just writing up an estimate along those lines. – robjohn Jul 8 '12 at 0:32

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.