Problem: For each integer $a_0 > 1$, define the sequence $a_0$, $a_1$, $a_2$,
\dots, by
\[
  a_{n+1} =
  \begin{cases}
    \sqrt{a_n} & \text{if $\sqrt{a_n}$ is an integer,} \\
    a_n + 3 & \text{otherwise}
  \end{cases}
\]
for each $n \ge 0$.
Determine all values of $a_0$ for which there is a number $A$
such that $a_n = A$ for infinitely many values of $n$.

Solution: The answer is $a_0 \equiv 0 \pmod 3$ only.

\paragraph{First solution.}
We first compute the minimal term of any sequence, periodic or not.

\begin{lemma*}
  Let $c$ be the smallest term in $a_n$.
  Then either $c \equiv 2 \pmod 3$ or $c = 3$.
\end{lemma*}
\begin{proof}
  Clearly $c \neq 1, 4$.
  Assume $c \not\equiv 2 \pmod 3$.
  As $c$ is not itself a square,
  the next perfect square after $c$ in the sequence
  is one of $\left( \left\lfloor \sqrt c \right\rfloor + 1\right)^2$,
  $\left( \left\lfloor \sqrt c \right\rfloor + 2\right)^2$,
  or $\left( \left\lfloor \sqrt c \right\rfloor + 3\right)^2$.
  So by minimality we require
  \[ c \le \left\lfloor \sqrt c \right\rfloor + 3 \le \sqrt c + 3 \]
  which requires $c \le 5$.
  Since $c \neq 1,2,4,5$ we conclude $c = 3$.
\end{proof}

Now we split the problem into two cases:

\begin{itemize}
\ii If $a_0 \equiv 0 \pmod 3$, then all terms of the sequence are $0 \pmod 3$.
The smallest term of the sequence is thus $3$ by the lemma
and we have \[ 3 \to 6 \to 9 \to 3 \]
so $A = 3$ works fine.

\ii If $a_0 \not\equiv 0 \pmod 3$,
then no term of the sequence is $0 \pmod 3$,
and so in particular $3$ does not appear in the sequence.
So the smallest term of the sequence is $2 \pmod 3$ by lemma.
But since no squares are $2 \pmod 3$,
the sequence $a_k$ grows without bound forever after,
so no such $A$ can exist.
\end{itemize}

Hence the answer is $a_0 \equiv 0 \pmod 3$ only.

\paragraph{Second solution.}
We clean up the argument by proving the following lemma.
\begin{lemma*}
  If $a_n$ is constant modulo $3$ and not $2 \pmod 3$,
  then $a_n$ must eventually cycle in the form
  $(m, m+3, m+6, \dots, m^2)$,
  with no squares inside the cycle except $m^2$.
\end{lemma*}
\begin{proof}
  Observe that $a_n$ must eventually hit a square, say $a_k = c^2$;
  the next term is $a_{k+1} = c$.
  Then it is forever impossible to exceed $c^2$ again,
  by what is essentially discrete intermediate value theorem.
  Indeed, suppose $a_\ell > c^2$ and take $\ell > k$ minimal
  (in particular $a_{\ell} \neq \sqrt{a_{\ell-1}}$).
  % We have $a_{\ell-1} \neq a_{\ell}^2$, since otherwise.
  Thus $a_{\ell-1} \in \{c^2-2, c^2-1, c^2\}$
  and thus for modulo $3$ reasons we have $a_{\ell-1} = c^2$.
  But that should imply $a_\ell = c < c^2$, contradiction.

  We therefore conclude $\sup \{a_n, a_{n+1}, \dots \}$ is a
  decreasing integer sequence in $n$.
  It must eventually stabilize, say at $m^2$.
  Now we can't hit a square between $m$ and $m^2$,
  and so we are done.
\end{proof}

Now, we contend that all $a_0 \equiv 0 \pmod 3$ work.
Indeed, for such $a_0$ we have $a_n \equiv 0 \pmod 3$ for all $n$,
so the lemma implies that the problem statement is valid.

Next, we observe that if $a_i \equiv 2 \pmod 3$,
then the sequence grows without bound afterwards
since no squares are $2 \pmod 3$.
In particular, if $a_0 \equiv 2 \pmod 3$ the answer is no.

Finally, we claim that if $a_0 \equiv 1 \pmod 3$,
then eventually some term is $2 \pmod 3$.
Assume for contradiction this is not so;
then $a_n \equiv 1 \pmod 3$ must hold forever,
and the lemma applies to give us a cycle of the form
$(m, m+3, \dots, m^2)$ where $m \equiv 1 \pmod 3$.
In particular $m \ge 4$ and
\[ m \le (m-2)^2 < m^2 \]
but $(m-2)^2 \equiv 1 \pmod 3$ which is a contradiction.