$x_1 = 2$, $x_{n + 1} = {{x_n(x_n + 1)}\over2}$, what can we say about $x_n \text{ mod }2$?
Let$$x_1 = 2, \quad x_{n + 1} = {{x_n(x_n + 1)}\over2}.$$What can we say about the behavior of $x_n \text{ mod }2$? Is there an exact formula for $x_n \text{ mod }2$?
It is not complete answer, but too long for comment.
First of all, for the sake of convenience let us define $y_n=x_{n+1}$, then, according to the algorithm in this paper recurrence $y_{n+1}=\frac{1}{2}y_n^2+\frac{1}{2}y_n$, $y_0=2$, has following solution: $$ y_n=\left\langle\textbf{e}\left|T_{jk}^n\right|\textbf{y}\right\rangle $$ Where $\langle\textbf{e}|=\{\delta_{j1}\}^\infty_{j=0}-$ row-vector, $\delta_{jk}-$ Kronecker symbol; $|\textbf{y}\rangle=\{2^j\}^\infty_{j=0}-$ column-vector; and $T-$ matrix, which elements defined as $T_{jk}=\left( \begin{array}{c} j \\ k-j \end{array} \right)2^{-j}$.
Components of $T_{jk}^n$ can be represented as: $$(T^n)_{i_{0}i_{n}}=\sum^\infty_{i_1=0}\sum^\infty_{i_2=0}...\sum^\infty_{i_{n-1}=0}T_{i_{0}i_{1}}T_{i_{1}i_{2}}...T_{i_{n-1}i_{n}}$$
However, we know that $\langle \textbf{e}|T^n_{jk}=\langle \textbf{e}|(T^n)_{jk}=T^n_{1k}$, hence we do not need all components, but only:
$$
(T^n)_{1i_n}=\sum^\infty_{i_1=0}\sum^\infty_{i_2=0}...\sum^\infty_{i_{n-1}=0}T_{1i_{1}}T_{i_{1}i_{2}}...T_{i_{n-1}i_{n}}
$$
Which leads to
$$
y_n=\sum^\infty_{i_n=0}\sum^\infty_{i_1=0}\sum^\infty_{i_2=0}...\sum^\infty_{i_{n-1}=0}T_{1i_{1}}T_{i_{1}i_{2}}...T_{i_{n-1}i_{n}}2^{i_n}
$$
And it's where hard part starts, hypergeometric functions popping up and so on.
Comparance to the expansion from initial reccurance. For example, consider the case of $x_3=y_2$: $$ y_2=\sum^\infty_{i_2=0}\sum^\infty_{i_1=0}\sum^\infty_{i_2=0}\left( \begin{array}{c} 1 \\ i_1-1 \end{array} \right)2^{-1}\left( \begin{array}{c} i_1 \\ i_2-i_1 \end{array} \right)2^{-i_1}2^{i_2}\to\\ y_2=\sum^\infty_{i_2=0}\left[\left( \begin{array}{c} 1 \\ i_2-1 \end{array} \right)2^{-2}+\left( \begin{array}{c} 2 \\ i_2-2 \end{array} \right)2^{-3}\right]2^{i_2}\to\\ y_2=\left[0\right]2^0+\left[2^{-2}\right]2^1+\left[2^{-2}+2^{-3}\right]2^2+\left[2*2^{-3}\right]2^3+\left[2^{-3}\right]2^4\to\\ y_2=0+2^{-1}+[1+2^{-1}]+2+2=6 $$ At the same time: $$ y_2=\frac{1}{2}y_1^2+\frac{1}{2}y_1\to\\ y_2=\frac{1}{2^3}\left[y_0^4+2y_0^3+y_0^2\right]+\frac{1}{2^2}\left[y_0^2+y_0\right]\to\\ y_2=[2+2+2^{-1}]+[1+2^{-1}] $$