Loops in a binary iterated function system

Question

Take a function $f(x)$ which operates on numbers written in binary. It is a three step operation:

1. Split the number into digits in even- and odd-numbered places. (For example, the number $\underline{1}1\underline{0}1\underline{0}$ becomes $[\underline{100},11]$. Underlines added for clarity.)
2. Concatenate the two sets of digits together, with the set containing the original first digit first. ($10011$)
3. Add one to this new binary number. ($10100$)

There are some numbers such that $f(x)=x$ ($10010$ for example). However, the sequence $a_0 = 1, a_{n+1} = f(a_{n})$, seems to remarkably miss all of them. I'm trying to prove that the sequence divereges, i.e. does not loop at any point. I don't know if this is the case, but I am confident.

I've checked the first million or so terms with a simple python program, which yeilds no counterexamples, however, that is far from a proof. I thought of doing induction on the numbers of the form $2^n$ (Since the function can never decrease the digit count, and only increases by 1, $2^n-1$ and $2^n$ are always part of the sequence (at least up to the point of a hypothetical repeat). If I can prove that $f(f(f(...f(2^n))...)))=2^{n+1}$, then that is enough to show there are no loops, however, I couldn't manage to. How can I prove this sequence divereges?

Answer 1

I scratch the proof as follows:

1. Given two numbers $a$ and $b$, $a\neq b \rightarrow f(a) \neq f(b)$ and vice versa.

2. Most of the time, $f(x)$ won't change the number of digits in binary form. So we have the following: considering the domain $A=[2^n-1,2^{n+1}-1]$, $f$ maps $A$ to domain $A'=[2^n,2^{n+1}]$.

This can be seen from $f(2^n-1)=2^n$. After that, the digit of the number in binary form won't decrease to n. And only one number in domain $A$ would give $2^{n+1}$, which is $2^{n+1}-1$. The other number in domain $A$ can only be mapped to a number within such range since the number of digits is fixed.

3. Considering our first statement, $f: A\rightarrow A'$ is a bijection mapping.

4. $f:\mathbf{N} \rightarrow \mathbf{N}^+$ is also a bijection mapping.

Consider the bijection mapping from $A$ to $A'$. There are $2^n+2$ distinct numbers($2^n-1$ to $2^{n+1}$). If we call $f(a)=b$ forms a directed link between $a$ and $b$, then there are $2^n+1$ directed links(the size of the domain), and it forms a graph $G$.

Consider the first statement, if we have a substructure of $G$: $a\rightarrow b \rightarrow c \rightarrow \ldots$, then it will never end on $b$ since no two numbers map to the same one. Then we can have:

5. $G$ is a vertex-disjoint union of one tree and loops.

A tree with $n$ nodes has $n-1$ links, and a loop with $n$ nodes have $n$ links(e.g., $[18\rightarrow 18]$, 1 node with 1 link point to self).

6. The structure $\ldots \rightarrow (2^n-1) \rightarrow 2^n \rightarrow \ldots $ is not a loop. So does $\ldots \rightarrow 2^{n+1}-1 \rightarrow 2^{n+1} \rightarrow \ldots$. Here we can conclude the sequence $a_0=1$ would never loop, and it will go through the set $\{1,2,4,8,\ldots\}$.

You can test the following statement:

7. All loops are within the domain $A$ for some $n$.

e.g., $n=4$. The structure is following:

$15 \rightarrow 16 \rightarrow 17 \rightarrow 21 \rightarrow 29 \rightarrow 31 \rightarrow 32 $

$18 \rightarrow 18$

$19 \rightarrow 22 \rightarrow 26 \rightarrow 20 \rightarrow 25 \rightarrow 23 \rightarrow 30 \rightarrow 28 \rightarrow 27 \rightarrow 24 \rightarrow 19$

The following is the old answer.

If $\underbrace{f(f(\ldots(f(x))))}_n= f^{n}(x)=x$, we say $x$ is a periodic point with period $n$.

It's easy to see the function f(x) has a period of 3, e.g.:

$[1579046, 1116710, 1312822, 1579046]$

And there are many other points with period 3. These period-3 points indicate there exists a period point for any period $n\in \mathbf{N^+}$. You can refer to Sharkovskii's theorem for detail.

Although there is a period point with an infinite large period, this is not easy to find. I checked your statement to $2^{30}=1073741824$, and it still holds.