3
$\begingroup$

Let $n$ be an integer more than $9$. Find the number of positive divisors of $n$ lets call it $d(n)$ and take the difference from $n$. So the new number is $n-d(n)$. If we continue this process, we always end up with $2$. I don't know anybody worked this question before but somehow this question reminded me Collatz Conjecture. Anybody can give me an idea how to approach this problem ? Many thanks..

$\endgroup$
  • $\begingroup$ Interesting ! Did you have the idea for this sequence ? $\endgroup$ – Peter Jun 20 at 8:10
  • 1
    $\begingroup$ Yes and no. I have been working on Collatz type series and one of my friend came to me and asked this question. You know collatz always ends up with 1 no matter where you start and this one always ends up with 2. I have a feeling that for n>10, we always end up with 2. $\endgroup$ – Turker Jun 20 at 8:19
  • $\begingroup$ I could not solve the question by induction method. If somebody can solve it and post it , I will be more than happy. $\endgroup$ – Turker Jun 20 at 8:22
  • 1
    $\begingroup$ Strictly spekaing, noone knows whether the Collatz-conjecture is true. In the case of this conjecture, I am optimistic that it can be proven. Brute force reveals that it is true upto $n=10^5$ $\endgroup$ – Peter Jun 20 at 8:31
  • $\begingroup$ Seems that Henry already solved it ... $\endgroup$ – Peter Jun 20 at 8:33
1
$\begingroup$

If $n < (k+1)^2$, there's at most $2k$ divisors here.

That's because if $x$ is a divisor of $n$ and greater than $\sqrt{n}$, the number $\frac{n}{x}$ must be an integer less than $\sqrt{n}$.

So there are only about $\sqrt{n}$ candidates for $x$, and it implies that the number of divisors is at most about $2\sqrt{n}$. More technically, $d(n)$ is at most $2k$.

The smallest $k$ here is exactly $\lfloor \sqrt{n} \rfloor$. So the upper bound of number of divisors is $2 \times \lfloor \sqrt{n} \rfloor$.

Now, let's check about when will $n - d(n) \geq 9$ hold.
Here, $n - d(n) \geq n - 2 \times \lfloor \sqrt{n} \rfloor \geq n - 2\sqrt{n} \geq 9$. The range of $n - 2 \sqrt{n} \geq 9$ can be solved by translating to quadratic equation.
Let $N = \sqrt{n}$. The inequality will be $N^2 - 2N \geq 9$, and it will be always true when $N \geq 1+\sqrt{10}$.

Now, we can say that $n - d(n) \geq 9$ when $n \geq 18 \geq (1+\sqrt{10})^2$.

The final winning run is to check validity for $n=9, 10, 11, 12, 13, 14, 15, 16, 17$ and we can do inductive proof for $n \geq 18$ because we proved that the next number will always be at least $9$.

$\endgroup$
0
$\begingroup$

Hints:

  • You can check it is true for $n=6,9,10,11,12$
  • For $n \gt 12$ you could show $9 \le n-d(n) \lt n$
  • Then use induction
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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