The doubling modulo \({\bf{1}}\) map defined by the equation \(\left( {\bf{9}} \right)\)exhibits some fascinating behavior. Compute the sequence obtained when

1. \({{\bf{x}}_0}{\bf{ = k / 7}}\)for\({\bf{k = 1,2, \ldots ,6}}\).
2. \({{\bf{x}}_0}{\bf{ = k / 15}}\)for\({\bf{k = 1,2, \ldots ,14}}\).
3. \({{\bf{x}}_{\bf{0}}}{\bf{ = k/}}{{\bf{2}}^{\bf{j}}}\), where \({\bf{j}}\)is a positive integer and \({\bf{k = 1,2, \ldots ,}}{{\bf{2}}^{\bf{j}}}{\bf{ - 1}}{\bf{.}}\)

Numbers of the form \({\bf{k/}}{{\bf{2}}^{\bf{j}}}\) are called dyadic numbers and are dense in \(\left( {{\bf{0,1}}} \right){\bf{.}}\)That is, there is a dyadic number arbitrarily close to any real number (rational or irrational).

For \({x_0} \in {\rm{(}}0,1{\rm{)}},\)

One has a map defined by:\({x_{n + 1}} = 2{x_n}\left( {\bmod \,1} \right) = \left\{ {\begin{aligned}{*{20}{l}}{2{x_n},\,\,{\rm{for}}\,\,0\pounds{x_n} < \frac{1}{2}}\\{2{x_n} - 1,\,\,{\rm{for}}\,\,\frac{1}{2}\pounds{x_n} < 1}\end{aligned}} \right.\)

In this case\({x_0} = \frac{k}{7}\), for\(k = \overline {1,6} \). So let's first\(k = 1\).

One has:

\(\begin{aligned}{c}{x_0} &= 1/7,\\{x_2} &= 2 \times \left( {1/7} \right)\left( {\bmod \,1} \right) = 2/7\\{x_3} &= 2 \times \left( {2/7} \right)\left( {\bmod \,1} \right) &= 4/7\\{x_4} &= 2 \times \left( {4/7} \right)\left( {\bmod \,1} \right) &= 8/7 - 1 &= 1/7\\{x_5} &= 2 \times \left( {1/7} \right)\left( {\bmod \,1} \right) &= 2/7, \ldots \end{aligned}\)

One obtained the sequence \(\left\{ {\frac{1}{7},\frac{2}{7},\frac{4}{7},\frac{1}{7}, \ldots } \right\}\)

For \(k = 2\) one has:

\(\begin{aligned}{c}{x_0} &= 2/7\\{x_1} = 2 \times \left( {2/7} \right)\left( {\bmod \,1} \right) &= 4/7\\{x_2} &= 2 \times \left( {4/7} \right)\left( {\bmod \,1} \right) &= 8/7 - 1 &= 1/7\\{x_3} &= 2 \times \left( {1/7} \right)\left( {\bmod \,1} \right) &= 2/7\\{x_4} &= 2 \times \left( {2/7} \right)\left( {\bmod \,1} \right) &= 4/7, \ldots \end{aligned}\)

Similarly, to the first case, one gets the sequence \(\left\{ {\frac{2}{7},\frac{4}{7},\frac{1}{7},\frac{2}{7}, \ldots } \right\}\)

Let \(k = 3\):

\(\begin{aligned}{l}{x_0} &= 3/7\\{x_1} = 2 \times \left( {3/7} \right)\left( {\bmod \,1} \right) = 6/7\\{x_2} &= 2 \times \left( {6/7} \right)\left( {\bmod \,1} \right) &= 12/7 - 1 &= 5/7\\{x_3} &= 2 \times \left( {5/7} \right)\left( {\bmod \,1} \right) &= 10/7 - 1 &= 3/7, \ldots \end{aligned}\)

Now, one gets the sequence \(\left\{ {\frac{3}{7},\frac{6}{7},\frac{5}{7},\frac{3}{7}, \ldots } \right\}\)

When \(k = 4\)one has

\(\begin{aligned}{l}{x_0} &= 4/7\\{x_1} &= 2 \times 4/7\left( {\bmod \,1} \right) &= 8/7 - 1 &= 1/7\\{x_2} &= 2 \times \left( {1/7} \right)\left( {\bmod \,1} \right) &= 2/7\\{x_3} &= 2 \times \left( {2/7} \right)\left( {\bmod \,1} \right) &= 4/7, \ldots \end{aligned}\)

So, once again one obtains the sequence \(\left\{ {\frac{4}{7},\frac{1}{7},\frac{2}{7},\frac{4}{7}, \ldots } \right\}\).

It is easy to see that for \(k = 5,{\bf{ }}k = 6\) one will obtain the second sequence, \(\left\{ {\frac{5}{7},\frac{3}{7},\frac{6}{7},\frac{5}{7}, \ldots } \right\}\) and \(\left\{ {\frac{6}{7},\frac{5}{7},\frac{3}{7},\frac{6}{7}, \ldots } \right\},\) for \(k = 5,{\bf{ }}k = 6,\)respectively, but one will do explicit calculation because this is the first example.

No one has that \({x_0} = k{\bf{ }}/{\bf{ }}15,\) where \(k = \overline {1,14} .\)Let's find the sequence for \(k = 1\,{\rm{:}}\)

\(\begin{aligned}{l}{x_0} &= 1/15\\{x_1} &= 2 \times \left( {1/15} \right)\left( {\bmod \,1} \right) &= 2/15\\{x_2} &= 2 \times \left( {2/15} \right)\left( {\bmod \,1} \right) &= 4/15\\{x_3} &= 2 \times \left( {4/15} \right)\left( {\bmod \,1} \right) &= 8/15\\{x_4} &= 2 \times \left( {8/15} \right)\left( {\bmod \,1} \right) &= 16/15 - 1 &= 1/15, \ldots \end{aligned}\)

So, one obtains the sequence \(\left\{ {1{\bf{ }}/{\bf{ }}15,2{\bf{ }}/{\bf{ }}15,4{\bf{ }}/{\bf{ }}15,8{\bf{ }}/{\bf{ }}15} \right\}\)and one can conclude that one will get the same sequence for \(k = 2,4,8.\)

When \(k = 3,\) one has

\(\begin{aligned}{l}{x_0} &= 3/15 &= 1/5\\{x_1} &= 2 \times \left( {1/5} \right)\left( {\bmod \,1} \right) &= 2/5 &= 6/15\\{x_2} &= 2 \times \left( {2/5} \right)\left( {\bmod \,1} \right) = 4/5 &= 12/15\\{x_3} &= 2 \times \left( {4/5} \right)\left( {\bmod \,1} \right) &= 8/5 - 1 &= 3/5 &= 9/15\\{x_4} &= 2 \times \left( {3/5} \right)\left( {\bmod \,1} \right) &= 6/5 - 1 &= 1/5 &= 3/15, \ldots \end{aligned}\)

For \(k = 3\) one gets the sequence \(\left\{ {1/5,2/5,4/5,3/5,1/5, \ldots } \right\}\)and one will get the same sequence for \(k = 6,12,9\).

Now, one will find the sequence for \(k = 5.\)

\({x_0} = 5{\bf{ }}/{\bf{ }}15 = 1{\bf{ }}/{\bf{ }}3,\)

\(\begin{aligned}{c}{x_1} &= 2 \times \left( {1/3} \right)\left( {\bmod \,1} \right) &= 2/3 &= 10/15,{\bf{ }}\\{x_2} &= 2 \times \left( {2/3} \right)\left( {\bmod \,1} \right) &= 4/3 - 1 &= 1/3 &= 5/15, \ldots \end{aligned}\)

So, for \(k = 5,10\)one has the sequence \(\left\{ {1/3,2/3,1/3, \ldots } \right\}.\)

When \(k = 7,\) one has:

\(\begin{aligned}{l}{x_0} &= 7/15,\\{x_1} &= 2 \times \left( {7/15} \right)\left( {\bmod \,1} \right) &= 14/15\\{x_2} &= 2 \times \left( {14/15} \right)\left( {\bmod \,1} \right) &= 28/15 - 1 &= 13/15\\{x_3} &= 2 \times \left( {13/15} \right)\left( {\bmod \,1} \right) &= 26/15 - 1 &= 11/15\\{x_4} &= 2 \times \left( {11/15} \right)\left( {\bmod \,1} \right) &= 22/15 - 1 &= 7/15, \ldots \end{aligned}\)

This gives us that for \(k = 7,14,13,11\)one has the sequence

\(\left\{ {7/15,14/15,13/15,11/15,7/15, \ldots } \right\}.\)

In this part \({x_0} = \frac{k}{{{2^j}}},\)where \(k = 1,2, \ldots ,{2^j} - 1\)and \(j\) is some positive integer. Let first \(k = 1\). Then

\(\begin{aligned}{c}{x_0} &= \frac{1}{{{2^j}}},\\{x_1} &= 2 \times \left( {\frac{1}{{{2^j}}}} \right)(\,\bmod \,1) &= \frac{1}{{{2^{j - 1}}}},\\{x_2} &= 2 \times \left( {\frac{1}{{{2^{j - 1}}}}} \right)(\,\bmod \,1) &= {2^2} \times \left( {\frac{1}{{{2^j}}}} \right)(\,\bmod \,1) &= \frac{1}{{{2^{j - 2}}}},\\M{x_{j - 1}} &= 2 \times \frac{1}{4}(\,\bmod \,1) &= {2^{j - 1}} \times \left( {\frac{1}{{{2^j}}}} \right)(\,\bmod \,1) &= \frac{1}{2},\end{aligned}\)

\(\begin{aligned}{c}{x_j} &= 2 \times \frac{1}{2}(\,\bmod \,1) &= {2^j} \times \left( {\frac{1}{{{2^j}}}} \right)(\,\bmod \,1) &= 1 - 1 &= 0,\\{x_{j + 1}} &= 2 \times 0(\,\bmod \,1) &= 0, \ldots \end{aligned}\)

One obtains that \({x_n} = 0\)for \(n \ge j\)and the sequence will be

\(\left\{ {1/{2^j},1/{2^{j - 1}}, \ldots ,1/2,0,0, \ldots } \right\}\)

When \(k = 2\) one has a similar problem: then \({x_0} = \frac{2}{{{2^j}}} = \frac{1}{{{2^{j - 1}}}},\) so in this case the sequence is \(\left\{ {1/{2^{j - 1}},1/{2^{j - 2}}, \ldots ,1/2,0,0, \ldots } \right\}\). In fact, whenever \(k\) is even, one will have that \({x_n} = 0\)for some \(n\). The bigger \(n\) is, one will have fewer non-zero values. So, one can claim with certainty that \({x_n} = 0\)when \(n \ge j\) for any event \(k\). One can expect that when \(k\) is odd one will have a similar sequence as when \(k\) is even.

Let \(k = {2^l} - 1\) for some \(l = \overline {2,j} .\)So \({x_0} = \frac{{\left( {{2^l} - 1} \right)}}{{{2^j}}}\) If \({x_0} < \frac{1}{2}\)then

\({x_1} = 2 \times {x_0}\left( {\bmod \,1} \right) = \frac{{2 \times \left( {{2^l} - 1} \right)}}{{{2^j}}}\left( {\bmod \,1} \right) = \frac{{\left( {{2^l} - 1} \right)}}{{{2^{j - 1}}}}\)

Again, if \({x_1} < \frac{1}{2}\) one will have that\({x_2} = 2 \times {x_1}\left( {\bmod \,1} \right) = {2^2} \times {x_0}\left( {\bmod \,1} \right) = \frac{{\left( {{2^l} - 1} \right)}}{{{2^{j - 2}}}}\)

One wants to know what happens when \({x_i} \ge \frac{1}{2},\)and one knows that at some point that must occur. Assume that \({x_{{n_0}}}\)is the first time one obtains a value that is greater or equal to \(\frac{1}{2}\). Let’s find the \({n_0}\)in terms of \(l\) and \(j\):

\({x_{{n_0}}} = 2 \times {x_{{n_0} - 1}}\left( {\bmod \,1} \right) = {2^{{n_0}}} \times {x_0} = \frac{{{2^{{n_0}}}\left( {{2^l} - 1} \right)}}{{{2^j}}} = \frac{{{2^l} - 1}}{{{2^{j - {n_0}}}}} > \frac{1}{2}\)

Multiplying the previous equation by \(2\)one will get:

So, now one has that\({x_{{n_0}}} = {2^{j - l}}\frac{{{2^l} - 1}}{{{2^j}}} = \frac{{{2^l} - 1}}{{{2^l}}}\)

Now, one has that:

\(\begin{aligned}{c}{x_{{n_0} + 2}} &= 2 \times {x_{{n_0} + 1}}\left( {\bmod \,1} \right) &= 2\frac{{{2^{l - 1}} - 1}}{{{2^{l - 1}}}} - 1 &= \frac{{{2^{l - 1}} - 1 - {2^{l - 2}}}}{{{2^{l - 2}}}}\\ = \frac{{{2^{l - 2}}\left( {2 - 1} \right) - 1}}{{{2^l} - 2}} &= \frac{{{2^{l - 2}} - 1}}{{{2^{l - 2}}}},\end{aligned}\)

\({x_{{n_0} + l}} = 2 \times {x_{{n_0} + l - 1}}\left( {\bmod \,1} \right) = \frac{{{2^{l - l}} - 1}}{{{2^{l - l}}}} = \frac{0}{1} = 0\)

\({x_{{n_0} + l + 1}} = 2 \times {x_{{n_0} + l}}\left( {\bmod \,1} \right) = 2 \times 0 = 0, \ldots \)

As expected, one has only finitely many non-zero values in the sequence when k is odd. Since \({n_0} + l\)is the first zero value, and \({n_0} = j - l,\) one has that the first zero value is for \(n = j + l - l = j\). This means that \({x_n} = 0\)for \(n \ge j\)for any \(k = 1,2, \ldots ,{2^j} - 1\)