Divisibility of sequence Let the sequence $x_n$ be defined by $x_1=1,\,x_{n+1}=x_n+x_{[(n+1)/2]},$ where $[x]$ is the integer part of a real number $x$. This is A033485. How to prove or disprove that 4 is not a divisor of any its term? The problem belongs to math folklore. As far as I know it, M. Kontsevich authors that. 

For $n\in\Bbb Z^+$ let $u_n=x_n\bmod 4$, and let $\oplus$ denote addition modulo $4$. We have the recurrences
$$\left\{\begin{align*}
u_{2n}&=u_{2n-1}\oplus u_n\\
u_{2n+1}&=u_{2n}\oplus u_n\;,
\end{align*}\right.$$
and the first few values are $u_1=1,u_2=2,u_3=3$, and $u_4=1$. The desired result is an immediate corollary of the following proposition.

Proposition. For all $n\in\Bbb Z^+$, $u_{4n}=u_n$, $u_{4n+1},u_{4n+3}\in\{1,3\}$, and $u_{4n+2}=2$. 

The proof is by induction on $n$. For $n>1$ we have
$$\begin{align*}
u_{4n}&=u_{4n-1}\oplus\color{blue}{u_{2n}}\\
&=\color{blue}{u_{4n-1}}\oplus u_{2n-1}\oplus u_n\\
&=\color{blue}{u_{4n-2}}\oplus 2u_{2n-1}\oplus u_n\\
&=\color{blue}{u_{4n-3}}\oplus 3u_{2n-1}\oplus u_n\\
&=\color{blue}{u_{4n-4}}\oplus u_{2n-2}\oplus 3u_{2n-1}\oplus u_n\\
&=\color{blue}{u_{n-1}\oplus u_{2n-2}}\oplus 3u_{2n-1}\oplus u_n\\
&=\color{blue}{4u_{2n-1}}\oplus u_n\\
&=x_n\;,
\end{align*}$$
where on each line I’ve highlighted in blue the term(s) to be manipulated to get the next line.
Then we have
$$\begin{align*}
&u_{4n+1}=u_{4n}\oplus u_{2n}=u_n\oplus u_{2n}=u_{2n+1}\in\{1,3\}\;,\\
&u_{4n+2}=u_{4n+1}\oplus u_{2n+1}=u_{2n+1}\oplus u_{2n+1}=2\;,\text{ and}\\
&u_{4n+3}=u_{4n+2}\oplus u_{2n+1}=2\oplus u_{2n+1}\in\{1,3\}\;,
\end{align*}$$
and the induction goes through.
