Collatz 3n+1 problem

Question

Does it suffice to say that, using the tree/reverse of 3n+1 problem, if we can show that we can generate all positive integers starting from integer 1, including 1 itself, is equivalent to proving indirectly the Collatz Conjecture?

Answer 1

We can indeed easily rephrase the Collatz conjecture to be about trying to generate every number starting from $1$ by applying a couple operations, but you have to be careful what you mean by "generate."

Let $f(x)=2x$ and $g(x)={x-1\over 3}$. It's natural to try to walk from $1$ to $n$ via $f$ and $g$ to show that $n$ isn't a counterexample to Collatz, but this doesn't always go smoothly: e.g. $g$ lets us map $13$ to $4$, but in a Collatz sequence we'll never go from $4$ to $13$ since $4$ is even (we would go instead from $4$ to $2$). So starting from $1$ and applying $f$ and $g$ repeatedly to get $n$ does not necessarily show that $n$ isn't a counterexample to Collatz, since when we reverse this walk we might get a sequence which doesn't follow the rules.

Specifically, we can never apply $g$ if the result will be even. The following is true:

Suppose there is a sequence $a_1,..., a_k$ with $a_1=1$, $a_k=n$, for each $i$ we have $a_{i+1}=f(a_i)$ or $a_{i+1}=g(a_i)$, and whenever $a_{i+1}$ is even we have $a_{i+1}=f(a_i)$. Then $n$ is not a counterexample to Collatz.

However, merely talking about "generating" numbers without this crucial restriction on when we're allowed to apply a given operation gives a very misleading idea.