Computing a sequence in the Cantor set

Question

Let $\eta:2^\omega\to 2^\omega$ be such that:

If $x \neq$ all 1's and $n$ is least such that $x_n=0$, then $\eta(x)=y$ where $$y_i=\begin{cases}x_i &\text{for } i>n\\ 1-x_i&\text{for }i\leq n.\end{cases}$$

I am interested in starting with the particular $x$ defined below. I believe this point corresponds to the number $1/4$ in the middle-thirds Cantor set $C\subseteq [0,1]$. Because $\sum_{k=1}^\infty \frac{2}{9^k}=1/4$.

\begin{align}x=&0101010101...\\ \eta(x)=&1101010101...\\ \eta^2(x)=&0011010101...\\ \eta^3(x)=&1011010101...\\ \eta^4(x)=&0111010101... \end{align}

QUESTION: Can you give a formula (closed form or recursive) for $\eta^n(x)$?

It's obvious that all the numbers will correspond to fractions in $C$, which might make for a nice equation(?). It's also true that you will never get the same number twice.

Here are the first few numbers:

$\frac{1}{4}$

$\frac{11}{12}$

$\frac{11}{108}$

$\frac{83}{108}$

$\frac{35}{108}$

$\frac{107}{108}$

$\frac{11}{972}$

...

maybe a pattern?

Answer 1

Applying $\eta$ to $y = 0000\dots$ instead would correspond to counting in binary, but backwards: \begin{align} y &= 0000\dots \\ \eta(y) &= 1000\dots \\ \eta^2(y) &= 0100\dots \\ \eta^3(y) &= 1100\dots \\ \eta^4(y) &= 0010\dots \end{align} This is closely related to sequence A030109 in the OEIS, and won't have a nice closed formula; you could write down the recurrence \begin{align} \eta^{2n}(y) &= \frac13 \eta^n(y), \\ \eta^{2n+1}(y) &= \frac13 \eta^n(y) + \frac23. \end{align}

When we start with $x$ instead of $y$, there's a trailing infinite sequence of $\dots1010101\dots$ that periodically throws us off. So the sequence $\eta^n(x)$ can be naturally broken up into block of length $4^k$ for $k=0, 1, 2, \dots$: in each of these blocks, we are copying $\eta(y)$ on the first $2k$ bits, followed by $110101\dots$.

More precisely, when $n = 1 + 4 + 4^2 + \cdots + 4^{k-1} + j$, for $1 \le j \le 4^k$, we have \begin{align} \eta^n(x) &= \eta^{j-1}(y) + \frac{2}{3^{2k+1}} + \sum_{i=k+1}^\infty \frac{2}{3^{2i}} \\ &= \eta^{j-1}(y) + \frac{11}{4 \cdot 3^{2k+1}}. \end{align} For example:

• If $n=5 = 1 + 4$, then $k=1$ and $j=4$, so we have $\eta^{n}(x) = \eta^{3}(y) + \frac{11}{108} = \frac{8}{9} + \frac{11}{108} = \frac{107}{108}$.
• If $n=6 = 1 + 4 + 1$, then $k=2$ and $j=1$, so we have $\eta^{n}(x) = \eta^{0}(y) + \frac{11}{972} = \frac{11}{972}$.

Answer 2

$\eta$ toggles all the bits up through the first zero in its argument. As a result, the first bit of $x$ toggles with every application of $\eta$. The second bit toggles unless the first bit is zero, so it goes through two $0$s and then two $1$s. The third bit will toggle when the first two bits are $1$, so will go through four $0$s followed by four $1$s and so on. The first four bits go through a cycle $$ \begin {align} &0000,1000,0100,1100,\\&0010,1010,0110,1110,\\&0001,1001,0101,1101,\\&0011,1011,0111,1111,\\ &0000,\ldots \end {align}$$ This cycle is just the reverse of the binary counting sequence. For any $x$, to get the bit string of $\eta^k(x)$ take a long enough leading part of $x$ that we won't carry out, reverse that part, add $k$ to the reversed leading part in binary, reverse the result, and append the infinite tail that we ignored.