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 https://blog.yhuang.org/?p=123 https://blog.yhuang.org/?p=123#comments Fri, 03 Oct 2008 13:01:53 +0000 admin http://scripts.mit.edu/~zong/wpress/?p=123 Here’s a problem posed to me by a friend:

Consider an equilateral triangle ABC with edge length 1. At each vertex is an object that is capable of movement at exactly speed 1. Beginning at time 0, each of the three objects moves toward its initial adjacent neighbor object, as in a game of pursuit. Of course, by symmetry, the objects will meet at the incenter of ABC. The question: how far will they have traveled?

The paths followed by the objects at first seem non-trivial, but in fact turn out to be nice. We will come back to this, but for the problem, the exact paths are irrelevant. We just need to find the amount of time it takes the objects to meet. The key part of the solution is to realize that, due to symmetry, the three objects always define an equilateral triangle at any time. Furthermore, their direction of motion is always along the edges of such a triangle, at speed v=1.

What we have is then a shrinking and rotating equilateral triangle that eventually decays to a point. Let us characterize this process.

At time \(t\), let \(s(t)\) be the length traveled by one of the objects. Let \(l(t)\) be the edge length of the triangle. Let \(A(t)\) be the area of the triangle. Then we have several relationships:

• \(\frac{ds}{dt}=1\)
• \(A(t)=\frac{\sqrt{3}}{4} l(t)^2\), and \(\frac{dA}{dt} = \frac{\sqrt{3}}{2} l(t) \frac{dl}{dt}\)
• By geometry, \(A(t+\Delta t) – A(t) = -3 (l(t) – \frac{ds}{dt} \Delta t) \frac{\sqrt{3}}{4} \frac{ds}{dt} \Delta t + o({\Delta t}^2)\), thus \(\frac{dA}{dt} = -3 \frac{\sqrt{3}}{4} l(t)\)

Combining: \(-\frac{3}{4}\sqrt{3} l(t) = \frac{\sqrt{3}}{2} l(t) \frac{dl}{dt}\)
\(\frac{dl}{dt} = -\frac{3}{2}\). Integrating with boundary conditions, we get \(-\frac{3}{2}t_f = -1\), \(t_f = \frac{2}{3}\), and since speed is 1, \(s(t_f) = t_f = \frac{2}{3}\). This is how far the object travels.

Finally, since the process is self-similar at every step along the path, the path of the object must be a logarithmic spiral. Furthermore, since the linear speed on the path is constant, the angular speed must be exponentially increasing (in angle) toward the center of the spiral.

To solve for this spiral explicitly, we have \(\frac{dr}{dt}=\frac{dr}{d\theta} \frac{d\theta}{dt} = \frac{\sqrt{3}}{3} \frac{dl}{dt} = -\frac{\sqrt{3}}{2}\).
\(\frac{dr}{d\theta} = -k \exp(-k \theta)\), so \(\frac{d\theta}{dt} = \frac{\sqrt{3}}{2k} \exp (k\theta)\), and \(\theta(t) = -\frac{1}{k} \ln(-\frac{\sqrt{3}}{2}t + C)\). Plugging into \(r(\theta) = \exp(-k\theta)\) and applying the boundary condition \(r(\theta_0) = \frac{\sqrt{3}}{3}\), we get \(r(t) = -\frac{\sqrt{3}}{2}t + \frac{\sqrt{3}}{3}\).
Next, \(\int_{\theta_0}^\infty r(\theta) d\theta = \frac{\sqrt{3}}{3k} = \frac{2}{3}\), so \(k=\frac{\sqrt{3}}{2}\) and \(\theta(t) = -\frac{2\sqrt{3}}{3} \ln(-\frac{\sqrt{3}}{2}t + \frac{\sqrt{3}}{3})\).