ATRACTOR

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.)