Analytic number theory question. Let $n$ be a positive integer, and define $f(n)$ as $n +\lfloor\sqrt{n}\rfloor$, where $\lfloor x\rfloor$ is the greatest positive integer less than or equal to $x$.  Prove that the sequence $n, f(n), f(f(n)), f(f(f(n))), \ldots$ contains a perfect square.
 A: Nice problem.  Define $g(n)$ to be the remainder when $n$ is divided by $\lfloor\sqrt{n}\rfloor$.  Also define $n_0 = n$, $n_{i+1}=f(n_i)$ for $i \geq 0$.  Consider the sequence $g(n_0), g(n_1), g(n_2), \ldots$.  We will prove that this sequence has infinitely many chunks of 0's separated by chunks of nonzero values.  Note that if $g(n_i) > 0$ while $g(n_{i+1}) = 0$, that means $n_{i+1}$ is a perfect square.  So we are essentially proving that the sequence $\{n_i\}$ has infinitely many perfect squares.
Let's set up notation first: suppose that $k^2 \leq n \leq (k+1)^2-1=k^2+2k$.  Note that when we go from $n$ to $f(n)=n+k$, we either cross $(k+1)^2$ or we don't.
Case 1: If we don't, $n+k < (k+1)^2$ and $\lfloor\sqrt{n+k}\rfloor=\lfloor\sqrt{n}\rfloor=k$.  Then it is clear that $g(n+k) = g(n)$.
Case 2: If we do, $n+k \geq (k+1)^2$ and $\lfloor\sqrt{n+k}\rfloor = \lfloor\sqrt{n}\rfloor+1 = k+1$.  This means $k^2+2k \geq n \geq k^2+k+1$.
If $g(n) = 0$, then $k|n$, so $n = k^2+2k$.  In this case $n+k = k^2+3k = (k+1)^2+(k-1)$, so $g(n+k) = k-1$.
If $g(n) > 0$ then $n = k^2+k+g(n)$.  Thus $n+k = k^2+2k+g(n) = (k-1)^2+g(n)-1$, which means $g(n+k) = g(n)-1$.
Putting things together: So each time we step forward by one in the sequence $\{g(n_i)\}$, one of three things happens.


*

*The value stays the same.

*If the value is positive, value decreases by one.

*If the value is zero, the value changes to some positive number.
Thus $\{g(n_i)\}$ will consist of chunks of zeros separated by chunks of nonzero values.  So $\{n_i\}$ contains infinitely many perfect squares, and the proof is complete!
(Let me know in the comments if I should clarify any of these steps.)
A: If $n$ is a square, you're done.  If $n=m^2+k$ with $0\lt k\lt2m+1$, then in either one or two steps you'll be at a number of the form $(m+1)^2+k'$ with $0\le k'\lt k$.  Induction (on $k$) now tells you that eventually you'll land on a square.
