Compositional Square

Let $\displaystyle n = k^2 + m, 2k+1 > m \geq 0$

Now, we get our hands dirty.

$\displaystyle f(n) = k^2 + m + \color{#D61F06} k$

$\displaystyle f(f(n)) = \left\{ \begin{array}{lr} k^2 + m+\color{#D61F06}{2k} & \text{if } 0 \le m < k+1\\ k^2 + m+\color{#D61F06}{2k+1} & \text{if } k+1 \le m < 2k+1 \end{array} \right.$

After this I am just writing, I am just writing the upper limits in the pieces the lower limits will change in a trivial manner because if they do then for that particular $m$ the square term would have already come.

$\displaystyle f^3(n) = \left\{ \begin{array}{lr} k^2 + m+\color{#D61F06}{3k + 1} & \text{if } m < k+1\\ k^2 + m+\color{#D61F06}{3k + 2} & \text{if } m < 2k+1 \end{array} \right.$

$\displaystyle f^4(n) = \left\{ \begin{array}{lr} k^2 + m+\color{#D61F06}{4k + 2} & \text{if } m < k+1\\ k^2 + m+\color{#D61F06}{4k + 4} & \text{if } m < 2k+1 \end{array} \right.$

$\displaystyle f^5(n) = \left\{ \begin{array}{lr} k^2 + m+\color{#D61F06}{5k + 4} & \text{if } m < k+1\\ k^2 + m+\color{#D61F06}{5k + 6} & \text{if } m < 2k+1 \end{array} \right.$

$\displaystyle f^6(n) = \left\{ \begin{array}{lr} k^2 + m+\color{#D61F06}{6k + 6} & \text{if } m < k+1\\ k^2 + m+\color{#D61F06}{6k + 9} & \text{if } m < 2k+1 \end{array} \right.$

It is not hard to see a pattern as -

We conjecture that

$\displaystyle f^{2t-1}(n) = \left\{ \begin{array}{lr} k^2 + m+\color{#D61F06}{(2t-1)k + (t-1)^2} & \text{if } m < k+1\\ k^2 + m+\color{#D61F06}{(2t-1)k + t(t-1)} & \text{if } m < 2k+1 \end{array} \right.$

$\displaystyle f^{2t}(n) = \left\{ \begin{array}{lr} k^2 + m+\color{#D61F06}{(2t)k + t(t-1)} & \text{if } m < k+1\\ k^2 + m+\color{#D61F06}{(2t)k + t^2} & \text{if } m < 2k+1 \end{array} \right.$

We need such that $f^{2t}(n)$ or $f^{2t-1}(n)$ is a square number.

Let's check.

Case 1

$k^2 + m + (2t-1)k + (t-1)^2 = (k+t-1)^2 + k + m$ cannot be a square.

$k^2 + m + (2t-1)k + t^2 - t = (k+t)^2 + m - k - t$ . So, for $t = m-k$ , we will get a square number.

There will exist a square number $\displaystyle \forall k+1 \le m < 2k+1$ at $\displaystyle f^{2(m-k) - 1}(n)$ where $n = k^2 + m$

Case 2

$k^2 + m + 2tk + t(t-1) = (k+t)^2 + m - t$ . So, for $t = m$ , we will get a square number

$k^2 + m + 2tk + t^2$ cannot be a square in the given domain.

There will exist a square number $\displaystyle \forall 0 \le m < k+1$ at $\displaystyle f^{2m}(n)$ where $n = k^2 + m$

We can now conclude this(I have not yet proved our conjecture and will also not do it).

Conclusion

If $\displaystyle f(n) = n + \left \lfloor \sqrt{n} \right \rfloor$ . And $n = k^2 + m ; 0\leq m <2k+1$ , then

the sequence $f(n), f^2(n), f^3(n),\cdots$ will always contain square of an integer.

In fact, the first such square will occur at, and its value will respectively be:

$\displaystyle \left\{ \begin{array}{lr} \text{at} f^{2m}(n) = (k+m)^2 & \text{if } 0 \leq m < k+1\\ \text{at} f^{2(m-k)-1}(n) = m^2 & \text{if } k+1 \geq m < 2k+1 \end{array} \right.$