Show that this fractal contains every odd, positive integer

Question

Let $f(x)=2x+\frac{1}{3}$

Let $g(x)=\frac{2x-1}{3}$

$f^n$ represents composition of $f$

Let $G_0=\{1\}$

Let $F_{m}=\{f^n(x):x\in G_{m}, n\in\mathbb{N_{\geq0}}\}$

Let $G_{m+1}=\{g(x):x\in F_m\}$

Show that for any given odd, positive integer $p$ there is some sufficiently high $m$ for which $p$ is in $F_m$

For what it's worth (and this may well not be helpful at all) but I've got some insight into why it's true but I can't translate that into a solution.

I can see that the denominator of $F_m$'s elements is a power of $3$ increasing with each successive $m$. I can see that these functions $f$ and $g$ (and restricted to the positive integers) form a Euclidean function where the orbits of $f$ and $g$ are in some sense orthogonal away from the vicinity of $1$.

I think this fact, combined with the fact that $F_m\cap F_{m-1}$ is somehow dense in the odd integers within the range from $G_m$ to $G_{m+1}$, proves the statement. But I have no idea by what metric $F_m\cap F_{m-1}$ are between $G_m$ and $G_{m+1}$.

I'm pretty sure it's a 2- and 3- adic number problem.

It is also a fact that this is a fractal. Each application of $F$ adds, for every element, a new set of numbers spaced exponentially, just above or below those already included.

Answer 1

Since $n=0$ is allowed, $\bigcup F_n$ is the set of numbers that ca be obtained by an arbitrary finite sequence of $f$ and $g$ from $1$. Thus the claim is that for every $p\in\Bbb N$, there exists a sequence $x_0,x_1,\ldots, x_N$ with $x_0=1$, $x_N=p$ and $x_{k+1}\in\{2x_k+\frac13, \frac{2x-1}3\}$.

Let $y_k=6x_k+2$. Then $y_0=8$, $y_N=6p+2$, and $y_{k+1}\in\{2y_k,\frac23 (y_k +1) \}$. We see that $y_k\in\Bbb Z[\frac13]$, and that $y_k\notin\Bbb Z$ implies $y_{k+1}\notin\Bbb Z$. As $y_N\in\Bbb Z$, we must have $y_k\in\Bbb Z$ for all $k$. In particular, $y_{k+1}=\frac23(y_k+1)$ is possible only if $y_k\equiv -1\pmod3$. We also see from this that all $y_k$ are even.

Let $z_k=-\frac12y_{N-k}\in\Bbb Z$. So $z_0=-3p-1$, $z_N=-4$ and $z_{k+1}\in\{\frac12z_k,\frac12(3z_k+1)\}$. Now the procedure becomes determined because me must have $z_{k+1}\in\Bbb Z$: If $z_k$ is odd, we must have $z_{k+1}= \frac12(3z_k+1)$, and if $z_k$ is even, we must have $z_{k+1}=\frac12z_k$. This allows us to extend the sequence beyond $z_N=-4$ as $$\tag1\ldots\to -4\to -2\to-1\to -1\to\ldots.$$ This reminds fatally of the (as of today unsolved) Collatz $3n+1$ problem, which states that for any positive integer $z_0$ we will end at $\ldots \to 1\to 2\to 1\to\ldots$ with the above recursion. (Collatz' original formulation splits the odd case into $z_{k+1}=3z_k+1$ and a necessarily following $z_{k+2}=\frac12z_{k+1}$). However, we are dealing with negative $z_0\equiv-1\pmod 3$ here, a slightly different problem. As far as I (and Wikipedia) know, this generalization to negative integers is also unsolved, but at least it is known that there are some additional limit cycles possible, namely apart from the $\ldots \to -1\to\ldots$ we are looking for at least also $$\tag2\ldots\to -5\to -7\to-10\to-5\to\ldots$$ and $$\tag3\ldots \to -17\to -25\to -37\to -55\to -82\to-41\to\\\to -61\to -91\to -136\to -68\to-34\to-17\to\ldots.$$ So our task is to show that for every $p\in\Bbb N$, the choice $z_0=-3p-1$ leads to $(1)$ and not to $(2)$ or $(3)$ or any as of now unknown cycle or unbounded behaviour. Unfortunately, $p=3$ leads to $z_0=-10$, leads to $(2)$, and we find many other such counterexmaples (e.g., $p=8$ leads to $(3)$). In other words, numbers such as $3$ or $8$ are not in any $F_m$.

Answer 2

This answer is a work in progress...

We need to show that the orbits of $f$ and $g$ are in some sense orthogonal in the positive, odd integers greater than $3$, or that they are in some sense Euclidean under composition in the same range.

The closed form for $f^n(x)$ is given by:

$$f^n(x)=2^nx+\frac{2^n-1}{3}$$

The closed form for $g^m(x)$ is given by:

$$g^m(x)=\left(\frac{2}{3}\right)^mx-\frac{1}{3}\sum_{k=1}^m\left(\frac{2}{3}\right)^{k-1}\\=\left(\frac{2}{3}\right)^m\cdot x+\left(\frac{2}{3}\right)^m-1\\=\left(\frac{2}{3}\right)^m(x+1)-1$$

If $f^n(x)=2^nx+\frac{2^n-1}{3}$ is an action of $\mathbb{N}$

Let $F_x=\{f^n(x)\mid n\in\mathbb{N}\}$ be the orbit of the point $x$ through $\mathbb{Q_{>2}}$ under this action.

And $g^m(x)=\left(\frac{2}{3}\right)^m(x+1)-1$ is also an action of $\mathbb{N}$

Let $G_x=\{g^m(x)\mid n\in\mathbb{N}\}$ be the orbit of the point $x$ through $\mathbb{Q}$ under this action.

To show that there is some metric space in which $F_{g^{-1}(x)}< F_x<F_{g(x)}$ for all $x\in F_x$ for all $F$ will prove the conjecture.

---

Update: Ok I've worked out that this metric space is a Euclidean combination of; the inequality:

$\log_2{x}-\lfloor\log_2{x}\rfloor>1-\log_2 3$

And the $2-$adic norm of $x$

I'm sorry if that's a bit vague; it needs more thought. Truth or otherwise of the inequality determines whether the highest power of $2$ which is less than the odd factors of any successor of any $F_{g^{-1}(x)}$, will be $4$ times that of its predecessor in $F_{g(x)}$, or only $2$ times.

The $2-$adic norm tells us whether the binary string of any $F_{g^{-1}(x)}$'s odd factors shrinks from the right by $1$ digit, or more.