Stuck at evaluating $\sum\limits_{d \mid n} \tau(d)$

158 Views Asked by At

It seems the number of nonnegative integer solutions to the equation $xyz=n$ is given by $$\sum\limits_{d \mid n} \tau(d)$$

$\tau$ is the number of divisors function. I'm wondering if there is a way to simplify this sum. Really appreciate any kind of help. Thank you.


Here is my attempt so far $$xyz = n$$

$x$ can be any of the factors of $n$ and the product $yz$ will be $n/x$. Since $yz$ sees all the factors of $n$, the number of nonnegative integer solutions to $xyz=n$ is simply the sum of divisors of the product $yz$.

Edit : Special thanks to @Tryss for identifying an error in the formula. I've fixed it now..

2

There are 2 best solutions below

1
On BEST ANSWER

The function $$f(n)=\sum_{d\mid n}\tau(d)$$ is multiplicative. That is, $f(mn)=f(m)f(n)$ whenever $\gcd(m,n)=1$.

Let's try to find a formula for powers of primes:

$$f(p^r)=\sum_{d\mid p^r}\tau(d)=\sum_{k=0}^r\tau(p^k)=\sum_{k=0}^r(k+1)=\frac{(r+1)(r+2)}2$$

Then, if the prime factorization of $n$ is $$n=\prod_{k=1}^sp_k^{t_k}$$ we have that $$f(n)=2^{-s}\prod_{k=1}^s(t_k+1)(t_k+2)$$

0
On

Factor $n$ as $p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha_k}$. Then every solution is associated with three vectors (the exponents in the factorizations of $x,y,z$) with non-negative integer components and sum given by $(\alpha_1,\ldots,\alpha_k)$. By stars and bars, it follows that the number of solutions is given by $$ \prod_{h=1}^{k}\frac{(\alpha_h+2)(\alpha_h+1)}{2}.$$