For a a ponsitive inreger $n$, let $d(n)$ denote the number of divisors of $n$. I'm trying to prove that:

1) For $n>6$ we have $d(n)\leq\frac{n}{2}$;

2) For $n>12$ we have $d(n)<\frac{n}{2}.$

Someone help me?

  • Please don't use $\sigma$ for the number of divisors (that should be the sum of the divisors). Use d(n) or $\tau(n).$ – Charles Dec 5 '14 at 15:09

The divisors of $n$ occur in pairs $(x,n/x)$. This implies that there is a divisor at most $\sqrt n$. Therefore $d(n)\le 2\sqrt{n}$. Now, $2\sqrt{n}< n/2$ if $n>16$. The case $6 < n\le 16$ is settled by inspection.

Let $n>12$ if $a$ is a divisor of $n$ then $a$ is not in the range $n/2 < a < n$ otherwise $n/a$ is an integer in the range $ 1 < n/a < 2$, in the same way $a$ can't be in the range $n/3 < a < n/2$, so the number of integers in this range is at least equal to the number of integers in the interval $[n/3,n-1]$ with the exception possibly of $n/2$ so it is at least $$ \left\lfloor n - 1 - \frac{n}{3} \right\rfloor -1 \ge n - \frac{n}{3} -2 = \frac{2}{3}n-2 $$ This means that the number of divisors of $n$ is at most $$d(n) \le n-\left( \frac{2n}{3}-2\right) = \frac{n}{3} + 2 $$ and this is smaller than $n/2$ if $n > 12$.

Let $n=\prod_{i=1}^k p_i^{\alpha_i}$, then we want $$\frac{d(n)}{n}=\frac{\prod_{i=1}^k{1+\alpha_i}}{\prod_{i=1}^k p_i^{\alpha_i}}\leq\frac{1}{2}$$ Look at just one term, and add 1 to the exponent of $p_i$ to observe that: $$\frac{\alpha+1}{p^\alpha}/\frac{\alpha+2}{p^{\alpha+1}}=\frac{1}{p}\left(1+\frac{1}{\alpha+1}\right)$$ So adding factors to $n$ makes $\displaystyle\frac{d(n)}{n}$ smaller, since $$\frac{1}{p}\left(1+\frac{1}{\alpha+1}\right)\leq \frac{1}{2}\left(1+\frac{1}{0+1}\right)=1$$ And in all the other cases we have a strict inequality. If we have a prime divisor $p\geq 5$, then $\displaystyle\frac{d(n)}{n}<\frac{1}{2}$, as the term of the product expressing $\displaystyle\frac{d(n)}{n}$ that belongs to $p_i$ has a "starting factor" smaller than $\frac{2}{5}<1/2$, and as we enlarge $\alpha_i$, $\frac{\alpha_i+1}{p_i^{\alpha_i}}$ get smaller, and all factors are at most $1$. For small $2^k3^n$ we have: $\frac{3}{3^2}=\frac{1}{3}$ and $\frac{4}{2^3}=\frac{1}{2}$. Since for $12$ the fraction is $1/2$ and for $18$ it is $1/3$, we are done (adding factors make the fraction smaller, and we checked the limit for $2^k3^n$, and we got that only $(0,1),(1,1),(2,0),(2,1),(3,0)$ is good.

A bound for the number of divisors of $n$ is given here: Bound for divisor function. We also have an effective upper bound as follows: $$ d(n)\le n^{\frac{1.5379 \log(2)}{\log(\log(n))}}, $$ for all $n\ge 3$. This is much better than what you want (for $n$ not too small, at least, i.e., $n\ge 41$; the case $n\le 40$ is settled by inspection).

  • see pdf bottom of book page 229 and top of book page 230. I do not believe the improved bounds on page 230 were ever published outside Guy's (1983) thesis, despite the fact that the second one gives a hard effective version of Wigert's lim sup result. – Will Jagy Dec 5 '14 at 19:29
  • 1
    @WillJagy Thank you for the interesting link! – Dietrich Burde Dec 5 '14 at 19:33
  • Actually Guy Robin, got the first and last names confused. – Will Jagy Dec 5 '14 at 19:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.