Analytic number theory question.

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.

Answer 1

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.

1. The value stays the same.

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

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

Answer 2

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.