2009/02/4
double log convergence
Here is a problem on complexity, or alternatively, convergence.
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\).
(Read the article)
