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. 

Prove by induction that modulo $4$,
$y_n = (x_n, (x_{2n-1}, x_{2n}, x_{2n+1}))$ is always one of the following quadruplets :
$(1,(1,2,3)) ;  (2,(1,3,1)) ; (2,(3,1,3)) ;  (3,(3,2,1))$
($x_n$ and $x_{2n-1}$ determine the other two values so this is also saying that $(x_n,x_{2n-1})$ can never be $(1,2),(1,3),(2,2),(3,1)$ or $(3,2)$)
We check that $y_1 = (1,(1,2,3))$.  
If $y_n = (1,(1,2,3))$ then since $1$ can only be followed by $2$ or $3$, either $x_{n+1} = 2$ and $y_{n+1} = (2,(3,1,3))$, either $x_{n+1} = 3$ and $y_{n+1} = (3,(3,2,1))$.
If $y_n = (3,(3,2,1))$ then since $3$ can only be followed by $1$ or $2$, either $x_{n+1} = 1$ and $y_{n+1} = (1,(1,2,3))$, either $x_{n+1} = 2$ and $y_{n+1} = (2,(1,3,1))$.
If $x_n = 2$ then $n = 2k$ and $y_k$ is $(1,(1,2,3))$ or $(3,(3,2,1))$.
In the first case we get $y_{n-1} = (1,(1,2,3)), y_n = (2,(3,1,3))$ and $y_{n+1} = (3,(3,2,1))$
In the other case we get $y_{n-1} = (3,(3,2,1)), y_n = (2,(1,3,1))$ and $y_{n+1} = (1,(1,2,3))$

Shape those quadruplet as a small triangle piece.
Here is the picture of the possible ways those pieces can interact : From the possible top and left pieces (determined by $x_n,x_{2n-1},x_{4n-3}$) we compute the other values and see that the next two pieces are still of the $4$ possible kind.

