# Number of positive integer divisors

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

• Interesting ! Did you have the idea for this sequence ? – Peter Jun 20 at 8:10
• 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. – Turker Jun 20 at 8:19
• I could not solve the question by induction method. If somebody can solve it and post it , I will be more than happy. – Turker Jun 20 at 8:22
• 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$ – Peter Jun 20 at 8:31
• Seems that Henry already solved it ... – Peter Jun 20 at 8:33

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

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