6
$\begingroup$

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}.$

  • 0
    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$)2012-07-07

1 Answers 1

8

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)$.

  • 0
    @hardmath: thanks! I was just writing up an estimate along those lines.2012-07-08