Number of divisors with even number of prime factors

I'm stuck with the following train of thought. Let $$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$$ s.t. the number of divisors is $$d(n)=(a_1+1)(a_2+1)\cdots(a_k+1)\,.$$ Now I want to find the size of the subset of divisors with only an even number of prime factors. Maybe there is a trivial thought, but currently I try to visualize it like this $$\underbrace{\bullet \bullet\cdots\bullet}_{a_1\times p_1} \quad \underbrace{\bullet \bullet\cdots\bullet}_{a_2\times p_2} \quad \cdots \quad \underbrace{\bullet \bullet\cdots\bullet}_{a_k\times p_k}$$ where in total there are $$a=a_1+a_2+...+a_k$$ dots. There is exactly 1 possibility to choose no prime factor and $$k$$ possibilities to choose $$1$$ prime factor (which is odd however). Now my idea was to count the number of divisors with $$m$$ prime factors and then sum over all even $$m$$. If all primes were distinct, then this would amount for $$\binom{a}{m}=\binom{k}{m}$$, which is the number of ways to choose $$m$$ primes out of $$a$$ distinct primes. In the current setup however, not all $$a$$ primes are distinct. How do I divide out the overcounting?

Let $$f(x) = \prod_{i=1}^k 1 + x+ \dots +x^{a_i}.$$ The quantity you want is the sum of the even coefficient of the polynomial $$f(x)$$, that is $$d = (f(1) + f(-1))/2$$. So, while $$f(1)$$ is the number of divisors $$d(n)$$, $$f(-1)$$ is either $$1$$ or $$0$$. Since $$d$$ must be integer anyway, the only choice is $$d = \lceil d(n)/2\rceil$$.

• So basically, if not all $a_i$ are even, then $f(-1)=0$ and $d=d(n)/2$. Otherwise $d=(d(n)+1)/2$. Commented Sep 18, 2022 at 19:30
• While this answers my first question, I leave the question open for a possible answer to the number of divisors with exactly $m$ primes. Commented Sep 18, 2022 at 20:18
• not doable in an elementary way. The number of partitions of $m$ given constrains on the single addends is too much complicated Commented Sep 18, 2022 at 20:22
• Yeah, the constraints may be the problem. If $m\leq a_i$ for all $i$, then it boils down to the number of (distinguishable) partitions of $m$, where all e.g. $1+1+2=4$ and $1+2+1$ are counted as separate partitions. Commented Sep 18, 2022 at 21:29

Let $$\Omega(n)$$ denote the number of prime factors of $$n$$ counted with multiplicities. Then we have

$$\sum_{\substack{m|d\\\Omega(m)\text{ even}}}1=\sum_{m|n}{1+(-1)^{\Omega(m)}\over2}=\frac12d(n)+\frac12\sum_{m|n}(-1)^{\Omega(m)}=\frac12d(n)+\frac12\prod_{i=1}^k{1-(-1)^{a_i}\over2}.$$

Since the right most term is always within $$[0,1/2]$$, we conclude that

$$\sum_{\substack{m|d\\\Omega(m)\text{ even}}}1=\left\lceil d(n)\over2\right\rceil.$$

• ceiling, not floor Commented Sep 18, 2022 at 20:00
• In the last step/equality of the first equation, do you use the same approach with $f(x)$ as in Exodds answer or how is the thought process here, $$\sum_{m|n} (-1)^{\Omega(m)} = \prod_{i=1}^k (1-1+1-1+...+(-1)^{a_i}) = \prod_{i=1}^k \frac{1+(-1)^{a_i}}{2} \, ?$$ Commented Sep 18, 2022 at 20:13
• @Exodd Edited. Thanks for pointing that out Commented Oct 24, 2022 at 8:35
• @Diger I am using the multiplicative property of Dirichlet convolutions Commented Oct 24, 2022 at 8:36