Find all positive integers $n$ such that $n$ is equal to $100$ times the number of positive divisors of $n$.
Problem
Source: Baltic Way 2000
Tags: inequalities, function, induction, number theory, prime factorization, number theory proposed
18.12.2010 06:56
I have a very ugly solution, but still a solution. Hope someone finds a nicer one. Here it goes: I use two well-known results: (i). Bernoulli's Inequality $(1+x)^n\geq 1+nx$ (i use it when $x=1$) (ii). $\tau (n) \leq 2\sqrt{n}$ where $\tau (n)$ stands for the number of divisors function Since $\tau (n) \leq 2\sqrt{n}$ then $100 \tau (n) \leq 200\sqrt{n}$ and since all the variables are positive $n \leq 200\sqrt{n}$ and $n\leq 40000$ If $n$ has at least 6 different prime divisors then $n\geq 2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}7^{\alpha_4}11^{\alpha_5}13^{\alpha_6}$ $\geq 2^{\alpha_1 +\alpha_2+2\alpha_3+2\alpha_4+3\alpha_5+3\alpha_6}$ $\geq 2^{\alpha_1 +\alpha_2+\alpha_3+\alpha_4+\alpha_5+\alpha_6}2^7$ $>100*2^{\alpha_1 +\alpha_2+\alpha_3+\alpha_4+\alpha_5+\alpha_6}$ $\geq100\tau(n)$ by (i). If $n$ has 5 different prime divisors then $n=2^{\alpha_1}5^{\alpha_2}p_{3}^{\alpha_3}p_{4}^{\alpha_4}p_{5}^{\alpha_5}$ $\geq100*p_{3}^{\alpha_3}p_{4}^{\alpha_4}p_{5}^{\alpha_5}$ It's easy to check that if $3\nmid n$ or if $7\nmid n$ then $n>40000$ So $n=2^{\alpha_1}5^{\alpha_2}3^{\alpha_3}7^{\alpha_4}p_{5}^{\alpha_5}$ If ${\alpha_1},{\alpha_2}>2$ or if ${\alpha_3},{\alpha_4},{\alpha_5}>1$, or even if $p_5>19$ then $n>40000$. So it remains to check the cases $n=2100*11, 2100*13, 2100*17, 2100*19$ (i haven't checked them yet sorry) Now if $n$ has 4 different prime divisors then $n=2^{\alpha_1}5^{\alpha_2}p_{3}^{\alpha_3}p_{4}^{\alpha_4}=100(\alpha_1 +1)(\alpha_2 +1)(\alpha_3 +1)(\alpha_4 +1)$ because $p_4|\alpha_i +1$ for some $i$ then $\alpha_i \geq p_4 -1 \geq 6$. If $\alpha_i\geq 6$ for $i\not=1$ then $n>40000$. So it remains to check the case $n=2^6$ and $\alpha_2=\alpha_3=\alpha_4=1$.(It's the only case where $n<40000$) If $n$ has 3 different prime divisors then $n=2^{\alpha_1}5^{\alpha_2}p_{3}^{\alpha_3}$ If $p_3\not=3$ then by the same argument above we must have one exponent being greater than or equal to 6, which makes $n>40000$ unless it is $\alpha_1=6$. If $n$ has only 2 different prime divisors then $n=2^{\alpha_1}5^{\alpha_2}=100(\alpha_1 +1)(\alpha_2 +1)$ and then $2^{\alpha_1 - 2}5^{\alpha_2 - 2}=(\alpha_1 +1)(\alpha_2 +1)$ with $\alpha_1,\alpha_2\geq3$ because if $\alpha_i=2$ then $3|2^k5^j$. By (i), we have $5^{\alpha_2 - 2}\geq4\alpha_2 -7 > \alpha_2 +1$ and by induction $2^{\alpha_1 -2}\geq\alpha_1 +1$ for $\alpha_1 \geq 5$. So $2^{\alpha_1}5^{\alpha_2}>100(\alpha_1 +1)(\alpha_2 +1)$ for $\alpha_1 \geq 5$ So we only need to check $\alpha_1 = 4$ and we are done. Sorry for not checking the cases! I was on a hurry when I solved the problem! I'll try to add them later
20.12.2010 21:09
I think it's possible to use the inequality $ \tau(n)\le \sqrt{3n} $. It gives the bound $ n\le 30000 $. A simple proof of this inequality can be found in http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=344684.
20.12.2010 22:41
Let $d(n)$ denote the number of divisors of $n$. We have that $n = 100 \times d(n)$. Using the prime factorization of $n$, we have that $n = 2^{k+2} \times 5^{t+2} \times p_1^{\alpha_1} \times p_2^{\alpha_2} \times ... \times p_m^{\alpha_m} = 100 \times d(n)$ $\Longleftrightarrow$ $2^{k+2}5^{t+2}p_1^{\alpha_1}p_2^{\alpha_2} ... p_m^{\alpha_m} = 100(k+2+1)(t+2+1)(\alpha_1 + 1) ... (\alpha_m + 1)$ $\Longleftrightarrow$ $2^k \times 5^t \times p_1^{\alpha_1} \times p_2^{\alpha_2} \times ... \times p_m^{\alpha_m} = (k+3) \times (t+3) \times (\alpha_1 + 1) \times ... \times (\alpha_m + 1)$, with $k, t \ge 0$ We can easily prove by induction that $p^{\alpha} > \alpha + 1$, $\forall p > 2$, therefore we must have $p_i = 1$, $\forall i$. On the same way, we can prove that $2^k > k+3$, $\forall k > 2$ and that $5^t > t+3$, $\forall t \ge1$. Then, the possible values for k are $0$, $1$ or $2$, and we must have $t = 0$, that is, $k+2 = 2,3$ or $4$, and $t+2 = 2$. So, $n = 2^25^2$, $n = 2^35^2$ or $n = 2^45^2$. By the $Brute Force Theorem$, we find that there is no value for $n$ satisfying the conditions.
21.12.2010 03:43
Max D.R. wrote: I think it's possible to use the inequality $ \tau(n)\le \sqrt{3n} $. It gives the bound $ n\le 30000 $. A simple proof of this inequality can be found in http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=344684. That would have done my work a lot easier hehe !! It's an interesting result, i wonder how much more can it be improved. I mean, what is the smallest $k$ such that $\tau(n)\leq k\sqrt{n}$ $\forall n\geq N$ for some $N$.
21.12.2010 10:26
Let \[n=\prod_p p^{a_p}\] and \[f(n)=\prod_pf_p(a_p), \ f_p(x)=\frac{p^x}{(x+1)}.\] Our equation is $f(n)=100$, therefore $a_2\ge 2,a_5\ge 2.$ Function $f_p(x)$ increase (for $p=2$,x>1). $f_2(2)=\frac{4}{3},f_5(2)=\frac{25}{3}$. Let $\prod_{p>5}f_p(a_p)=A.$ Then $f_3(a_3)A\le 9.$ If $A\not =1$, then $A\ge \frac 72.$ $f_5(4)>100$, therefore $a_5=3$ or $a_5=3$. Case $a_5=3$. If $a_5=3$, then $f_5(3)=\frac{125}{4}$ and $\prod_{p\not =5}f_p(a_p)=\frac{16}{5}.$ Therefore $a_2\ge 4$ It gives $a_2\le 4$ and $n=2^4*5^3$ is solution. Therefore case $a_5=3$ gives unique solution $n=2000.$ Case $a_5=2$. Then $\prod_{p\not =5}=f_p(a_p)=12$. Therefore $a_3\ge 1$, if $a_2=2$, then $a_3\ge 2$. Case $a_5=2=a_2$ gives $f_3(a_3)A=9$. If $a_3=3$, then $A=\frac{4}{3}$. Because $f_p(x)\ge \frac{p}{2}$ for $x\ge 2$ we had contradition. If $a_3=2$, then $A=3<\frac{7}{2}$ - contradition. It mean $a_2>2$. Case $a_5=2,a_2=3$. Therefore $f_3(a_3)A=6\to a_2>3$. Case $a_5=2, a_2=4$. $f_3(a_3)A=\frac{15}{4}.$ Because $a_3\ge 1$ we get $A=1$ - no solution. For $a_5=2, a_2\ge 5$ we get $f_3(a_3)A\le \frac{9}{4}\to A=1\to a_3\le 2$ - no solution.
22.12.2010 03:04
On the problem of finding the smallest $k$ such that $ \tau(n)\leq k\sqrt{n} $, I don't know the solution. That is a interesting question, I think.
02.10.2013 19:44
What is the Brute Force theorem?