If an integer \(n\) is reduced by the largest square less than it each time until it is terminated at zero, show that the number of steps taken is at most order \(\log \log n\).

More precisely, let \(f(n) = n – {\left\lfloor{\sqrt{n}}\right\rfloor}^2\) and \(g(n)=k\) be the minimum number of steps until \(f^k(n)=0\). Prove that there exists some fixed \(A\) such that \(g(n)< A \log \log n\) for all \(n\ge 3\).

Why is the convergence speed double log? Well, it really has to do with the fact that the remainder \(f(n)\) is of order square root of \(n\), and that ultimately has to do with the fact that the gaps between successive integer squares grow linearly. Each time \(f\) is applied to some \(n\), the remainder after the removal of the largest square is no more than the gap value between that square and the next square.

The proof goes something like this. \(m^2 – (m-1)^2 = 2m – 1 < 2m\), so \(f(n) \le (\left\lfloor{\sqrt{n}}\right\rfloor + 1)^2 - {\left\lfloor{\sqrt{n}}\right\rfloor}^2 < 2({\left\lfloor{\sqrt{n}}\right\rfloor + 1}) \le 2\sqrt{n} + 2 \le 4\sqrt{n}\), where the last step is valid for \(n \ge 1\). After applying \(f\) some \(k\) times iteratively, we get \(f^k(n) < \underbrace{4\sqrt{\cdots 4\sqrt{4\sqrt{n}}}}_k = 16^{\frac{1}{2} + \frac{1}{4} + \cdots + 2^{-k}} n^{2^{-k}} < 16 n^{2^{-k}}\).

Now, if for some \(k\), \(16 n^{2^{-k}} < 17\), then certainly there must be some \(K \le k\) such that the integer \(f^K(n) \le 16\), in which case the total number of steps to terminate is no more than \(k+4\). (For the 4, see graph below for termination cases for \(n\le 16\).)

Next we solve \(16 n^{2^{-k}} < 17 \) (*) for \(k\) by taking log twice, and using the monotonicity of log:

Clearly, if \(k > \frac{\log \log n}{\log 2}\), then (*) is satisfied, so the total number of steps required to terminate is given by \(g(n) \le \frac{\log \log n}{\log 2} + 4 < 44 \log \log n\) for \(n\ge 3\), QED.

]]> https://blog.yhuang.org/?feed=rss2&p=156 0