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.


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$.

  • $\begingroup$ Did u spot it's only odd integers? Also, I think it needs solving by means of the fact the orbits of the two functions are in some sense orthogonal and they form a Euclidean function over some p-adic metric space. This is much simpler than Collatz because it's not limited by the restriction to integers which introduces switching between functions. $\endgroup$ – samerivertwice Apr 13 '17 at 20:06
  • $\begingroup$ ...and $g(f^2(1))=3$ $\endgroup$ – samerivertwice Apr 13 '17 at 21:07

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:


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.