## The dynamics of a trick

### Proof

In base $$2$$, $$f_{D,2}$$ has $$2^{\frac{D}{2}}$$ cycles of period $$1$$.

Let us consider the natural numbers written in base $$2$$ and the transformation $$f_{D,2}$$ acting in binary representations with $$D$$ digits, with zeros allowed at the left. The domain of $$f_{D,2}$$ has $$2^{D}$$ elements; the image is reduced to $$\frac{3^{\frac{D}{2}}+1}{2}$$ elements when $$D$$ is even and has $$\frac{3^{\frac{D-1}{2}}+1}{2}$$ elements if $$D$$ is odd.

For $$D=2$$, the image of $$f_{2,2}$$ has $$2$$ elements, $$\{00, 01\}$$, and these are fixed points of the transformation. The orbit of any other element of the domain of $$f_{2,2}$$ ends in one of these fixed points after one iteration.

For $$D=4$$, the image of $$f_{4,2}$$ has $$5$$ elements, namely $$\{0000, 0111, 0101, 0010, 1001\}$$ and, from these, the first four are fixed points; the orbit of $$1001$$ ends in $$0000$$ after one iteration. Again, the orbit of any element of the domain of $$f_{4,2}$$ ends in one of these fixed points. The fixed points are determined by solving the equation $$f_{4,2}(n)=n$$, where $$a_{3}a_{2}a_{1}a_{0}$$ is the binary representation of $$n$$ $$(a_{j}$$ is $$0$$ or $$1).$$ The equation is reduced to the two following equalities: $7\,(a_{3}-a_{0}) + 2\,(a_{2}-a_{1})= 8a_{3} + 4a_{2} + 2a_{1} + a_{0}$ or $7\,(a_{0}-a_{3}) + 2\,(a_{1}-a_{2})= 8a_{3} + 4a_{2} + 2a_{1} + a_{0}.$

The first equation is equivalent to $$a_{3} + 2a_{2} + 4a_{1} + 8a_{0} = 0$$, and from there we get $$a_{3}=0=a_{2}=a_{1}=a_{0}$$, thus obtaining the fixed point $$0$$ of $$N_{4}$$. The second equation can be rewritten as $5a_{3} = 2\,(a_{0} - a_{2})$ from which we get $$a_{1}$$ is free in $$\{0,1\}$$ and that $$a_{3}=0$$ (so that $$5a_{3}$$ can be even), whence $$a_{0} = a_{2}$$. Hence, the fixed points of $$f_{4,2}$$ are the binary representations $$0a_{0}a_{1}a_{0}$$. That is, $$0000, 0010, 0111, 0101.$$

For $$D=6$$, we deduce by a similar process that the fixed points of $$f_{6,2}$$ are the binary representations $$0a_{0}a_{1}a_{2}a_{1}a_{0}$$, where $$a_{0},$$ $$a_{1}$$ and $$a_{2}$$ are free in $$\{0,1\}$$; we obtain $$8$$ fixed points. The image of $$f_{6,2}$$ contains $$14$$ elements and all orbits end in one of these fixed points.

In general, let us suppose that $$D$$ is even, and let us determine the fixed points of $$f_{D,2}$$. For that purpose, we only need to solve the equation $$f_{D,2}(n)=n$$, with $$a_{D-1}a_{D-2}...a_{1}a_{0}$$ being the binary representation of $$n$$ with $$D$$ digits $$0$$ or $$1$$. This equation is equivalent to the two following equalities: $(2^{D-1} - 1)(a_{D-1}-a_{0}) + (2^{D-2} - 2)(a_{D-2}-a_{1}) +...+\left (2^{\frac{D}{2}} - 2^{\frac{D}{2}-1}\right)\left(a_{\frac{D}{2}}-a_{\frac{D}{2}-1}\right) =\\ 2^{D-1}a_{D-1} + 2^{D-2}a_{D-2} +...+ 2^{\frac{D}{2}}a_{\frac{D}{2}} +...+ 2a_{1} + a_{0}$ or $(2^{D-1} - 1)(a_{0}-a_{D-1}) + (2^{D-2} - 2)(a_{1}-a_{D-2}) +...+ \left(2^{\frac{D}{2}} - 2^{\frac{D}{2}-1}\right)\left(a_{\frac{D}{2}-1}-a_{\frac{D}{2}}\right) =\\ 2^{D-1}a_{D-1} + 2^{D-2}a_{D-2} +...+ 2^{\frac{D}{2}}a_{\frac{D}{2}} +...+ 2a_{1} + a_{0}. (*)$ The first equation is equivalent to $a_{D-1} + 2a_{D-2} +...+ 2^{D-2}a_{1} + 2^{D-1}a_{0} = 0$ and from there we conclude that $$a_{D-1}=0=a_{D-2}=...=a_{1}=a_{0}$$, thus obtaining the fixed point $$0$$ of $$N_{D}$$. The second equation is equivalent to $$i_{D,2}(x)=2x$$ and can be rewritten as $2^{D-1}a_{0} + 2^{D-2}a_{1} + ... + 2a_{D-2} + a_{D-1} = 2\,\left(2^{D-1}a_{D-1} + 2^{D-2}a_{D-2}+...+ 2^{\frac{D}{2}}a_{\frac{D}{2}}+...+2a_{1} + a_{0}\right)$ from where we immediately deduce that we must have $$a_{D-1} = 0$$, otherwise we would obtain an odd natural on the left side of the equation and a even natural on the right side. Therefore, equation (*) is reduced to $2^{D-2}a_{0} + 2^{D-3}a_{1}+...+ 2a_{D-3} + a_{D-2} = 2^{D-1}a_{D-1} + 2^{D-2}a_{D-2}+...+ 2^{\frac{D}{2}}a_{\frac{D}{2}}+...+2a_{1} + a_{0}\,\, (2*)$ and from this we conclude, by a reasoning similar to the one previously given, that we must have $a_{D-2} = a_{0}.$

That allow us to reformulate (2*) as $2^{D-3}a_{0} + 2^{D-4}a_{1}+…+2a_{D-4} + a_{D-3} = 2^{D-2}a_{D-1} + 2^{D-3}a_{D-2}+…+ 2^{\frac{D}{2}-1}a_{\frac{D}{2}}+…+2a_{2} + a_{1}$ and therefore we should have $$a_{D-3} = a_{1}$$. Keeping with this argument, we obtain the general expression for the binary representation of a fixed point of $$f_{D,2}:$$ $0 a_{D-2} a_{D-3} … a_{\frac{D}{2}} a_{\frac{D}{2}-1} a_{\frac{D}{2}} a_{\frac{D}{2}-1}… a_{D-3} a_{D-2}$ where $$a_{D-2}, a_{D-3}, … ,a_{\frac{D}{2}-1}$$ and $$a_{\frac{D}{2}}$$ are free in $$\{0,1\}$$. Therefore, we have found $$2^{\frac{D}{2}}$$ fixed points. (Note that, until $$D=16$$, all orbits of $$f_{D,2}$$ end in one of these fixed points.)