2
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
4
  • $\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$
    – Diger
    Sep 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$
    – Diger
    Sep 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$
    – Exodd
    Sep 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$
    – Diger
    Sep 18, 2022 at 21:29
1
$\begingroup$

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. $$

$\endgroup$
4
  • $\begingroup$ ceiling, not floor $\endgroup$
    – Exodd
    Sep 18, 2022 at 20:00
  • $\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$
    – Diger
    Sep 18, 2022 at 20:13
  • $\begingroup$ @Exodd Edited. Thanks for pointing that out $\endgroup$
    – TravorLZH
    Oct 24, 2022 at 8:35
  • $\begingroup$ @Diger I am using the multiplicative property of Dirichlet convolutions $\endgroup$
    – TravorLZH
    Oct 24, 2022 at 8:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .