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?
2 Answers
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$.
-
$\begingroup$ So basically, if not all $a_i$ are even, then $f(-1)=0$ and $d=d(n)/2$. Otherwise $d=(d(n)+1)/2$. $\endgroup$– DigerSep 18, 2022 at 19:30
-
$\begingroup$ While this answers my first question, I leave the question open for a possible answer to the number of divisors with exactly $m$ primes. $\endgroup$– DigerSep 18, 2022 at 20:18
-
$\begingroup$ not doable in an elementary way. The number of partitions of $m$ given constrains on the single addends is too much complicated $\endgroup$– ExoddSep 18, 2022 at 20:22
-
$\begingroup$ 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. $\endgroup$– DigerSep 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. $$
-
-
$\begingroup$ 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} \, ?$$ $\endgroup$– DigerSep 18, 2022 at 20:13
-
$\begingroup$ @Exodd Edited. Thanks for pointing that out $\endgroup$ Oct 24, 2022 at 8:35
-
$\begingroup$ @Diger I am using the multiplicative property of Dirichlet convolutions $\endgroup$ Oct 24, 2022 at 8:36