Upper limit for the Divisor function

Question

For a a positive integer $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}.$

Can someone help me?

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.