The dynamics of a trick

Proof

Let us consider natural numbers $$B\geq 2$$ and $$D$$, the representations of the naturals in base $$B$$ and the transformation $$f_{D,B}: N_{D} \rightarrow N_{D}$$ previously defined. One has:

(a) There is a natural $$D$$ such that the function $$f_{D,B}$$ has non-null fixed points if and only if $$B$$ is not congruent to $$1$$ modulo $$3$$.

(b) If $$f_{D,B}$$ has a non-null fixed point, then it has a representation $$a_{D-1}a_{D-2}...a_{1}a_{0}$$ in base $$B$$ verifying:

- if $$B$$ is a multiple of $$3$$, then $$a_{D-1} = 0$$ and $$a_{0} = 0$$, or $$a_{D-1} = \frac{B}{3}$$ and $$a_{0} = \frac{2B}{3}$$;

- if $$B$$ is congruent to $$2$$ modulo $$3$$, then $$a_{D-1}=0$$ and $$a_{0}=0$$, or $$a_{D-1}=\frac{B-2}{3}$$ and $$a_{0}=\frac{2B-1}{3}$$.

In particular, in base $$10$$, $$f_{D}$$ has only one fixed point, $$0$$, for every $$D$$.

Let us fix a natural $$B\geq 2$$ (a base) and an even natural $$D$$. The fixed points of the transformation $$f_{D,B}$$ are the solutions $$n$$ of the equation $$f_{D,B}(n)=n$$, or, equivalently, of the equations $$i_{D}(n)=n$$ and $$i_{D}(n)=2n$$. Let $$a_{D-1}a_{D-2}...a_{1}a_{0}$$ be the representation of $$n$$, in base $$B$$, with $$D$$ digits of $$\{0,1,...,B-1\}$$. These equations are equivalent to the next two equalities: $(B^{D-1} - 1)(a_{D-1}-a_{0}) + (B^{D-2} - B)(a_{D-2}-a_{1}) +...+\left (B^{\frac{D}{2}} - B^{\frac{D}{2}-1}\right)\left(a_{\frac{D}{2}}-a_{\frac{D}{2}-1}\right) =\\ B^{D-1}a_{D-1} + B^{D-2}a_{D-2} + ... + B^{\frac{D}{2}}a_{\frac{D}{2}} +...+ Ba_{1} + a_{0}$ or $(B^{D-1} - 1)(a_{0}-a_{D-1}) + (B^{D-2} - B)(a_{1}-a_{D-2}) +...+\left (B^{\frac{D}{2}} - B^{\frac{D}{2}-1}\right)\left(a_{\frac{D}{2}-1}-a_{\frac{D}{2}}\right) =\\ B^{D-1}a_{D-1} + B^{D-2}a_{D-2} + ... + B^{\frac{D}{2}}a_{\frac{D}{2}} +...+ Ba_{1} + a_{0}.$

The first equation is equivalent to $a_{D-1} + Ba_{D-2} + ... + B^{D-2}a_{1} + B^{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 it can be rewritten as $B^{D-1} a_{0} + B^{D-2} a_{1} + ... + B a_{D-2} + a_{D-1} = \\B^{D-1}(2a_{D-1}) + B^{D-2}(2a_{D-2}) +...+ B^{\frac{D}{2}}\left(2a_{\frac{D}{2}}\right) +...+ B(2a_{1}) + 2a_{0}. \mbox{(#)}$

We hence have an equality between a representation in base $$B$$, on the left side, and a sum of powers of $$B$$ between $$0$$ and $$D-1$$ with coefficients which are two times the coefficients of $$n$$, on the right side. We then immediately deduce some necessary conditions for $$n$$ to be a fixed point:

• $$B$$ must divide $$2a_{0} - a_{D-1}$$;
• if $$n$$ is a non-null fixed point, then the reverse $$i_{D}(n)$$ must be an even natural (in base $$10$$);
• if $$a_{0} = 0$$, then $$a_{D-1} = 0$$;
• $$a_{D-1} < \frac{B}{2}$$ (otherwise we would have a remainder from $$2a_{D-1}$$ and, therefore, a nonzero summand with the power $$B^{D}$$ in the right side of the equality);
• if $$a_{0} \neq 0$$, then

- if $$2a_{0}$$ has more than two digits in base $$B$$, then the digit $$a_{D-1}$$ is the last digit of the representation of $$2a_{0}$$ in base $$B$$;
- $$2a_{D-1} = a_{0}$$ or $$2a_{D-1} + 1 = a_{0}$$.

From the first and the last of these conditions, we also deduce that:

• Either $$a_{0}$$ is even, equal to $$2a_{D-1}$$, and $$B$$ divides $$3a_{D-1}$$.

In this case, since $$0\leq a_{D-1}\leq B-1$$ and $$a_{D-1} < \frac{B}{2}$$, we have only two possibilities for the equation $$3a_{D-1} = Bk$$ with $$k$$ a non-negative integer (since it implies $$0\leq k<\frac{3}{2}$$): either $$k=0$$, and then $$a_{D-1} = 0$$ and $$a_{0} = 0$$; or $$k=1$$ and $$a_{D-1} = \frac{B}{3}$$, which is only possible if $$B$$ is a multiple of $$3$$, and $$a_{0} = \frac{2B}{3}$$.

• Or $$a_{0}$$ is odd, equal to $$2a_{D-1} + 1$$, and $$B$$ divides $$3a_{D-1} + 2$$.

In this case, $$B$$ can not be a multiple of $$3$$, otherwise the prime $$3$$ would divide $$3a_{D-1} + 2$$, and would therefore be a divisor of $$2$$. Moreover, since $$0\leq a_{D-1}\leq B-1$$ and $$a_{D-1} < \frac{B}{2}$$, only one nonnegative integer value $$k$$ satisfies the equality $$3a_{D-1} + 2 = Bk$$: $$k=1$$ and $$a_{D-1}=\frac{B-2}{3}$$, which is only possible if $$B$$ is congruent to $$2$$ modulo $$3$$, and, therefore, $$a_{0} = \frac{2B-1}{3}$$. Indeed, $$0\leq k\leq 2$$ (because we should have $$\frac{3B}{2} + 2 > Bk$$, that is, $$k < \frac{3}{2} + \frac{2}{B} \leq \frac{3}{2} + \frac{2}{2} = \frac{5}{2}$$); and, if $$k=0$$, the equality $$3a_{D-1} + 2 = Bk$$ is not possible; if $$k=2$$, then $$a_{D-1} = 2\frac{B-1}{3}$$, an equality which is valid only if $$B$$ is congruent to $$1$$ modulo $$3$$ (whence $$B\geq 4$$), and $$a_{0} = \frac{4B-1}{3} = B + \frac{B-1}{3} \geq B + 1$$, which is not allowed to a digit in base $$B$$.

Let us see two examples. Consider $$D=2$$ and $$B=2$$. Since $$B$$ is congruent to $$2$$ modulo $$3$$, the previous reasoning indicates how to build a non-null fixed point $$a_{1}a_{0}$$: it is enough to consider $$a_{1} = \frac{B-2}{3} = 0$$ and $$a_{0} =\frac{2B-1}{3} = 1$$. And indeed $$01$$ is a fixed point of $$f_{2,2}$$. Let us now fix $$D=2$$ and $$B=3$$. The previous reasoning indicates that if the representation $$a_{1}a_{0}$$ in base $$B$$ is a fixed point, then $$a_{1} = \frac{B}{3} = 1$$ and $$a_{0} = \frac{2B}{3} = 2$$. But $$12$$ (in base $$3$$) is not a fixed point because the reverse of $$n$$ is $$21$$, which is odd (in base $$10$$). When $$D=2$$ and $$B=6$$, a candidate to a fixed point is $$24$$ (in base $$6$$), but, despite being even, it does not verify the equality (#). In general, if $$B$$ is a multiple of $$3$$, then $$f_{2,B}$$ does not have non-null fixed points because such points would have to be represented by $$a_{1}a_{0}$$, with $$a_{1} = \frac{B}{3}$$ and $$a_{0} = \frac{2B}{3}$$, and verify the equality (#), which in this case is $B a_{0} + a_{1} = B\,(2a_{1}) + 2a_{0}$ that is, $B\frac{2B}{3} + \frac{B}{3} = B\frac{2B}{3} + \frac{4B}{3}$ $\frac{1}{3}= \frac{4}{3}.$

On the contrary, when $$B$$ is congruent to $$2$$ modulo $$3$$, the transformation $$f_{2,B}$$ has one (and only one) non-null fixed point: it is represented in base $$B$$ by $$a_{1}a_{0}$$, with $$a_{1} = \frac{B-2}{3}$$ and $$a_{0} = \frac{2B-1}{3}$$, which verifies equality (#) since $\begin{array}{cl} & Ba_{0}+a_{1}=B\,\left(2a_{1}\right)+2a_{0}\\ \Leftrightarrow & B\frac{2B-1}{3}+\frac{B-2}{3}=B\left(2\frac{B-2}{3}\right)+2\frac{2B-1}{3}\\ \Leftrightarrow & 0=0 \end{array}$

The condition that $$B$$ is not congruent to $$1$$ modulo $$3$$, which is necessary for the existence of some even $$D$$ such that $$f_{D,B}$$ has a fixed point distinct of $$0$$, is also a sufficient condition. Let us consider such a natural $$B\geq 2$$; it only remains to guarantee the existence of such a fixed point for values of $$B$$ which are multiples of $$3$$. Let us search it for $$f_{4,B}$$.

Let $$a_{3}a_{2}a_{1}a_{0}$$ be an element of $$N_{4}$$ in base $$B$$. To verify whether it is a fixed non-null point, we must analyze one of the following cases.

Case 1: $$a_{3} = 0$$ and $$a_{0} = 0$$.

Equality (#) $B^{3} a_{0} + B^{2} a_{1} + B a_{2} + a_{3} = \\ B^{3}\times 2a_{3} + B^{2}\times 2a_{2} + B\times 2a_{1} + 2a_{0}$ is reduced to $B^{2}a_{1} + B a_{2} = B^{2}\times 2a_{2} + B\times 2a_{1}$ that is, $B a_{1} + a_{2} = B\times 2a_{2} + 2a_{1}$ an equation which, in order that one obtains a non-null fixed point, imposes that $$a_{1} = \frac{2B}{3}$$ and $$a_{2} = \frac{B}{3}$$. However, as we have seen, these values do not satisfy the equality (#).

Case 2: $$a_{3} =\frac{B}{3}$$ and $$a_{0} = \frac{2B}{3}$$.

The equality (#) reads now as $B^{3} \frac{2B}{3} + B^{2} a_{1} + B a_{2} + \frac{B}{3} =\\ B^{3}\frac{2B}{3} + B^{2}\times 2a_{2} + B\times 2a_{1} + \frac{4B}{3}$ that is, $B^{2} a_{1} + B a_{2} = B^{2}\times 2a_{2} + B\times 2a_{1} + B$ which is reduced to $B a_{1} + a_{2} = B\times 2a_{2} + 2a_{1} + 1.$

This equation can now be analyzed as (#), thus obtaining

• $$B$$ must divide $$2a_{1} + 1 - a_{2}$$;
• $$a_{1}\neq 0$$;
• $$a_{2} < \frac{B}{2}$$;
• $$2a_{2} = a_{1}$$ or $$2a_{2} + 1 = a_{1}$$.

From the first and last of these conditions we conclude that:

• Either $$a_{1}$$ is even, equal to $$2a_{2}$$, and $$B$$ divides $$3a_{2} + 1$$.

But, since $$0\leq a_{D-2}\leq B-1$$ and $$a_{2} < \frac{B}{2}$$, the equality $$3a_{2} + 1 = Bk$$ for a nonnegative integer $$k$$ implies that $$k < \frac{3}{2} + \frac{1}{B} \leq \frac{3}{2} + \frac{1}{2} = 2$$, from which it follows that $$k$$ may be equal to $$0$$ (a value which is not allowed because $$3a_{2} + 1$$ is not zero) or $$k=1$$ (a value which is not allowed because, by hypothesis, $$B$$ is not congruent to $$1$$ modulo $$3$$).

• Or $$a_{1}$$ is odd, equal to $$2a_{2} + 1$$, and $$B$$ divides $$3a_{2} + 3$$.

Since $$0\leq a_{D-2}\leq B-1$$ and $$a_{D-2} < \frac{B}{2}$$, we only have one admissible value for a nonnegative integer $$k$$ satisfying the equality $$3a_{2} + 3 = Bk$$: $$k=1$$, and therefore $$a_{2} = \frac{B}{3}-1$$ and $$a_{1} = \frac{2B}{3}$$. That is, $$f_{4,B}$$ has one (and only one) non-null fixed point, with representation in base $$B$$ given by $\left(\frac{B}{3}\right)\left(\frac{B}{3}-1\right)\left(\frac{2B}{3}-1\right)\left(\frac{B}{3}\right).$

For example, if $$B=6$$, then the number $$2134$$ is the non-null fixed point of $$f_{4,6}$$.