How to find $\sum_{d\mid n}(w(d)w(\frac{n}{d}))$?

Question

i) $w(n)$ is the prime divisor count function. For example $w(6)=2$

ii) Let prime factorization of $n=p_{1}^{a_{1}}p_{2}^{a_{2}}.....p_{w(n)}^{a_{w(n)}}$

iii) Lets define this function.

$$f(n)=\sum_{d\mid n}(w(d)w(\frac{n}{d}))$$

iv) How to write $f(n)$ with $w(n),a_{1},a_{2},...a_{w(n)}$ . Seems like a hard combinatorics question.(Hard for me...) If n is squarefree its easy to find the answer.

Answer 1

I changed the notation by mistake, in the following the $\alpha$s are the multiplicities of the primes, and I define $w=w(n)$ (for short) and $\Pi_\alpha = \prod_k (\alpha_k-1)$. We evaluate the contributions that are simple to evaluate in three steps:

1. For each combination of $k$ primes with multiplicity among $w$ in total, the contribution is $k(w-k)$, so the total contribution for these terms is $$\sum_{k=1}^{w} \binom{w}{k} k (w-k)$$

2. For each combination of $k$ primes, $1\leq l< k$ of which with multiplicity, the contribution is $k(w-l)$. If $(\varphi_1, ..., \varphi_{k-l})$ denote the indices of the $k-l$ remaining primes (ie the indices "$i$" of the alphas), then there are $\prod_{m=1}^{k-l}(\alpha_{\varphi_m}-1)$ ways of picking these remaining primes, so the total contribution for these terms is $$\sum_{k=2}^{w} \sum_{l=1}^{k-1} \binom{w}{k} \left( \prod_{\varphi\in\binom{k}{l}} \prod_{m=1}^{k-l}(\alpha_{\varphi_m}-1) \right) k(w-l) = \\ \sum_{k=2}^{w} \binom{w}{k} \sum_{l=1}^{k-1} {\Pi_\alpha}^{\binom{k-1}{l}} k(w-l)$$ where the last equality says that each prime among the $k$ will not get selected with full multiplicity $\binom{k-1}{l}$ times (I'm not entirely confident with this one).

3. For each combination of k primes, none of which with full multiplicity, the contribution is $kw$. With the previous notations, there are $\prod_{m=1}^{k}(\alpha_{\varphi_m}-1)$ ways of picking such primes, so the total contribution of these terms is $$\sum_{k=1}^{w}\left( \prod_{\varphi\in\binom{w}{k}}\prod_{m=1}^{k}(\alpha_{\varphi_m}-1) \right) kw = \sum_{k=1}^{w} {\Pi_\alpha}^{\binom{w-1}{k-1}} kw$$ where the last equality says that each prime gets selected $\binom{w-1}{k-1}$ times.

I think I have them all, and that I didn't count any twice. If so, $f(n)$ is the sum of these three sums. This should be equivalent to AlexR's answer $$f(n) = \sum_{a\in\mathbb{N}^{w},\ a\leq\alpha_i} (w-\text{nz}(a))(w-\text{nz}(\alpha-a))$$

which is quite elegant; it simply says that each prime composing $d$ counts in $w(d)$, but only those with full multiplicity (hence the $\alpha-a$) count in $w(n/d)$. Even though the latter summation is huge as it is written, I can think of a way to compute this in $O(3^w)$, but my answer is more efficient with a complexity of $O(w^2)$.