This question already has an answer here:

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.


marked as duplicate by heropup, rtybase, Matthew Conroy, Namaste, JonMark Perry May 24 '17 at 2:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What are your thoughts, what efforts can you present to us here? $\endgroup$ – complexmanifold May 23 '17 at 13:13
  • $\begingroup$ If $n = a^2-b$ with $b\le 2a$ then $\lfloor\sqrt{n}\rfloor = a-1$ and $f(n) = a^2-b+a-1$ $\endgroup$ – reuns May 23 '17 at 13:42
  • $\begingroup$ We should look instead at $f(n) = n +2\lfloor\sqrt{n}\rfloor+1$ ? $\endgroup$ – reuns May 23 '17 at 13:46
  • $\begingroup$ Does not seem to be true for $n=5$ ... $5,8,11,15,19,24,\cdots $ ... every second one seems to be one shy of the next square. $\endgroup$ – Donald Splutterwit May 23 '17 at 13:46
  • $\begingroup$ interesting. @Do $\endgroup$ – G.H.Hardy May 23 '17 at 15:31

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

  • $\begingroup$ I see that 2 and 3 definitely form a loop. However, can you clarify or prove anywhere that the case of 1 is eventually proceeded by a case of 2 or 3? Perhaps I'm being really dense here. I just want to be sure there isn't the case of "infinite cases of 1 in a row" $\endgroup$ – The Great Duck May 24 '17 at 4:31
  • $\begingroup$ @TheGreatDuck The sequence is always increasing since $n$ is positive so $\lfloor\sqrt{n}\rfloor$ is also positive. Could you clarify what you mean by a loop? $\endgroup$ – fractal1729 May 24 '17 at 21:22
  • $\begingroup$ Case 1: "The value stays the same." What I'm asking is what proof have you given that case 1 doesn't add up to a value that also falls into case 1 that also adds up to a value that falls into case 1... infinitely $\endgroup$ – The Great Duck May 24 '17 at 23:49
  • 1
    $\begingroup$ Sorry, I didn't realize you were referring to $\{g(n_i)\}$ instead of $\{n_i\}$. The reason that won't happen is that since $\{n_i\}$ is increasing, you will eventually cross a perfect square, which forces one of 2 or 3 to happen. $\endgroup$ – fractal1729 May 25 '17 at 1:29

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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.