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}.$$
Can someone help me to evaluate or at least to approximate the following sum.
-
1It looks to be a multiplicative function, and the result for prime powers is somewhat tractable. Have you already looked at it to that extent? – 2012-07-07
-
0To 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
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)$.
-
0An 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$. – 2012-07-08
-
0@hardmath: thanks! I was just writing up an estimate along those lines. – 2012-07-08