# A problem involving the inverse Collatz map

Let $C$ be the Collatz map on the natural numbers, defined by: $$C(n) := \begin{cases} n/2 & \text{if} \;n \;\text{even} \\ (3n+1)/2 & \text{if} \;n \;\text{odd} \end{cases}$$
The inverse of $C$ is: $$C^{-1}(\{n\}) = \begin{cases} \{2n\} & \text{if} \;n \not \equiv 2 \pmod 3 \\ \{2n, (2n-1)/3\} & \text{if} \;n \equiv 2 \pmod 3 \end{cases}$$ Let $n$ be a natural number with $n \equiv 2 \pmod 3$. Let $C^{-k}$ be $C^{-1} \circ \cdots \circ C^{-1}$ ($k$ times).
Consider the cardinals $c_1(n,k):= \vert C^{-k}(\{2n\}) \vert$ and $c_2(n,k):= \vert C^{-k}(\{(2n-1)/3\}) \vert$.

Question: Is it true that $\forall n \equiv 2 \pmod 3$, $\exists k>0$ such that $c_1(n,k) \neq c_2(n,k)$?
Remark: It is checked for $n \le 10^8$.

Assuming the answer is no, let $n$ be a counter-example.
Motivation-Question: Is $n$ also a counter-example of the Collatz conjecture?

Assuming the answer is yes, let $\alpha$ be the map defined by:
$$\alpha (n) := \begin{cases} 1 & \text{if} \;n \not \equiv 2 \pmod 3 \\ 1+\min\{k>0 \ \vert \ c_1(n,k) \neq c_2(n,k) \} & \text{if} \;n \equiv 2 \pmod 3 \end{cases}$$

By looking to the graph below, we get for example that $\alpha(8)=2$ and $\alpha(20)>3$.

A natural number $N$ is called a champion if $\forall n<N$ we have $\alpha(n)<\alpha(N)$.
Below is the list of the first champions (read as $[N,\alpha(N)]$):

[2, 4]
[20, 6]
[182, 8]
[1640, 10]
[14762, 12]
[132860, 14]
[1195742, 16]
[10761680, 18]
[96855122, 20]


Observation: Two consecutive champions $N$ and $N'$ in the finite list above satisfy the relations: $N'=9N+2$ and $\alpha(N')=\alpha(N)+2$.

Bonus question: Is the list of champions exactly $(N_r)_{r \ge 1}$ with $N_r = \frac{9^r-1}{4}$ and $\alpha(N_r) = 2r+2$?

Remark: I don't know whether $N_r = \frac{9^r-1}{4}$ is champion $\forall r \ge 10$; but I have checked that $\alpha(N_r) = 2r+2$, $\forall r \le 26$, and we can confidently conjecture that it is true in general (the proof should be workable using the fact that the base-$9$ representation of $N_r$ is $222 \cdots 2$).

• Sequence appears here: oeis.org/A125857 – Fred Kline Dec 19 '17 at 11:05
• Yes, it is the sequence of numbers whose base-$9$ representation is $22222222.......2$. It is nice to see that they appear in several other mathematical subjects. – Sebastien Palcoux Dec 19 '17 at 13:46
• It would be great if you could establish a link with prime gaps, which on average also grow logarithmatically. – Sylvain JULIEN Dec 19 '17 at 19:45

What is $k_n$ (the ones you checked for $n \le 10^8$)?

Some thought on the champions, but I didn't dig much yet:

I think the tree must be symmetric up to $[k-1]$ (I'll come to symmetry later), you could still have $c1=c2$ without symetry, but it would probably not hold with the other rules (e.g. alternance). I have to check.

For visual purpose, I put the "$\{2n\}$" leafs on the left in the left part of the tree, and on the right in the right part of the tree. I put multiple of $3$ in red, and circled the "$n \equiv 2 \pmod 3$".

I call "symmetric counterparts" elements which map to each other in the symmetry (e.g. $69$ and $213$ are symmetric counterparts. $80$ and $26$ are symmetric counterparts). For the symmetry to be kept, every counterparts must be of the same value modulo $3$ ($0$, $1$ or $2$).

From the example above, you can see that the symmetry is lost on the $2^{k-2}-1=7$ element, which is not $\equiv 2 \pmod 3$ like its counterpart $23$, so it has one child less.

It is well known that in a Collatz sub-sequence starting with $2^a-1$, you will always climb up to $3^a-1$ in $a$ steps, which is the largest "forward sub-sequence" up to this $n=2^a-1$, so my guess is that having a champion has something to do with that (especially knowing that the forward sub-sequence must have a symmetric counterpart of the same kind, which is the case as shown bellow).

So for the example above, on the left of the tree we have a forward sub-sequence starting with $2^{k-1}-1=15$: $\{15,23,35,53,80\}$, ending with $3^{k-1}-1=80$, and on the right, the (almost) symmetric counterpart sub-sequence starting with $2^{k-2}-1=7$: $\{7,11,17,26\}$, ending with $3^{k-2}-1=26$.

Note that $[k-1]$ is even since $[k+1]=\alpha (n)$ is even, so $3^{k-1}-1$ can be rewritten $9^{\frac{k-1}{2}}-1$, and from there you divide by $4$ to reach $n=20$ which leads to your formula $n=\frac{9^{\frac{k-1}{2}}-1}{4}$. The $\{(2n-1)/3\}$ element ($13$ in the example) is therefore $\frac{(2\cdot\frac{9^{\frac{k-1}{2}}-1}{4})-1}{3}=\frac{(\frac{3^{k-1}-1}{2})-1}{3}=\frac{3^{k-2}-1}{2}$ and the parent ($26$) is therefore $3^{k-2}-1$ which we know leads up to $2^{k-2}-1=7$ but in 1 step less than its counterpart, which gives a symmetry break ($2^a-1$ is not $\equiv 2 \pmod 3$ like its successors).

For the symmetry part, I still have to look, but perhaps this kind of thing might do the trick:mod 18 (probably depends on $k$)

I also have to look at other possible "symmetry breaks", and probably draw some other cases to find some rules as soon as I have more time.

• Welcome to mathoverflow! Thanks for your investigation! $k_n$ is just a positive integer depending on $n$. The formulation of the question was probably confusing, I have clarified it. – Sebastien Palcoux Dec 23 '17 at 23:18