The binary Collatz dynamics of the trinomials $x^n+x+1$: proof of two conjectures of Gallardo and Rahavandrainy

Gallardo and Rahavandrainy studied an analogue of the Collatz map on $\mathbb{F}_2[x]$, in which $x(x+1)$ plays the role of $2$ and $x^2+x+1$ that of $3$: an odd polynomial $A$ is sent to the odd part of $1+(x^2+x+1)A$. They proved that every orbit reaches $1$, and conjectured that the orbit of the trinomial $x^n+x+1$ has length $2^s+1$, where $s$ is the largest integer with $2^{s+1}<n$, and that for $1\le t\le s-1$ it contains $2^t$ terms of the same degree. We prove both statements for every $n\ge3$. The proof rests on the identity $(x^2+x+1)+x(x+1)=1$: it reduces the dynamics to a map from one plateau to the next, characterises the last plateau of any orbit, and shows that along the orbit of $x^n+x+1$ the plateaus start at the $2^j$-th powers of the odd parts of the polynomials $x^m(x^2+x+1)+1$, the index $m$ following an explicit binary recursion. We also note that a later restatement of the conjecture, with a non-strict inequality, fails exactly when $n$ is a power of $2$. A script checks all the statements numerically.