**Update**: See end of post.

Having abandoned my previous approach, I have found another computer-assisted approach to the problem that should heuristically work and which is not subject to the obstructions of my previous approach.

Define a *legal move* to be an affine function $x \mapsto ax+b$ that is the composition of a finite number of the maps $x \mapsto \frac{x}{2}$ and $x \mapsto 3x+1$ (allowing repetitions). For instance, $x \mapsto \frac{9x+a}{4}$ will be a legal move for $a = 4, 5, 7, 8, 10, 15, 16$, and more generally legal moves take the form $x \mapsto \frac{3^n x + a}{2^m}$ for some natural numbers $n,m,a$ with $a$ not divisible by $3$ (except when $n=0$). Note that while the generating moves $x \mapsto \frac{x}{2}$ and $x \mapsto 3x+1$ can map integers to half-integers, which can in turn be mapped to other dyadic rationals (rationals whose denominator is a power of 2), they cannot turn half-integers (or other non-integer dyadic rationals) back into integers. Hence if a legal move takes an natural number $x$ to a natural number $y$, all intermediate steps in that move must also be natural numbers, and so $y$ can be reached from $x$ by a relaxed Collatz iteration. Since one can of course get from any power of $2$ to $1$ by a legal move, and one can use $x \mapsto 3x+1$ to get from a multiple of $3$ to a non-multiple of $3$, the relaxed Collatz conjecture now follows from

**Conjecture** Given any natural number $x_0$ that is not a multiple of $3$, there exists a power of $2$ that is reachable from $x_0$ by a legal move.

In the previous approach the strategy was to iterate $x_0$ to something smaller. Here we will take the opposite approach of instead making $x_0$ *larger* in search of a power of two, but taking advantage of the flexibility available in the relaxed setting to "aim" where the iterates go to a certain extent.

More specfically, I claim that the above conjecture follows from the following (in principle numerically verifiable) claim.

**Claim** There exists $n,m$ with $3^n > 2^m$ and an interval $[a_-,a_+]$ of length at least $4 \times 3^n$ such that $x \mapsto \frac{3^n x + a}{2^m}$ is a legal move for every natural number $a \in [a_-,a_+]$ that is not a multiple of $3$.

Indeed, suppose that we have verified this claim for some $n,m$. Then we have

**Interval expansion lemma** If $[x_-, x_+]$ is an interval with $x_-, x_+$ natural numbers (excluding the degenerate case when $x_-=x_+$ is a multiple of $3$), then every natural number $y$ in the interval $[ \lceil \frac{3^n (x_-+1)+a_-}{2^m} \rceil, \lfloor \frac{3^n (x_+-1)+a_+}{2^m} \rfloor]$ that is not a multiple of $3$, can be reached by a legal move from some natural number in $[x_-,x_+]$ that is not a multiple of $3$.

**Proof** It suffices to show that $y$ is reachable by legal moves from two consecutive elements of $[x_-, x_+]$ (or just one, if $x_-=x_+$). From the claim, $y$ is reachable from any $x$ with
$$ \frac{3^n x + a_-}{2^m} \leq y \leq \frac{3^n x + a_+}{2^m}$$
(the fact that those $\frac{3^n x + a}{2^m}$ with $a$ divisible by $3$ are omitted from the claim is not an issue here since these only generate multiples of $3$, and $y$ is assumed not to be a multiple of $3$). This constraint restricts $x$ to an interval. By the hypothesis on $y$, the right endpoint of this interval is at least $x_-+1$ and the left endpoint is at most $x_+-1$, so the intersection of this interval contains two consecutive elements of $[x_-,x_+]$ (or just one, if $x_-=x_+$), giving the lemma. $\Box$

Note that if $[x_-,x_+]$ has length $h$, then the new interval
$[ \lceil \frac{3^n (x_-+1)+a_-}{2^m} \rceil, \lfloor \frac{3^n (x_+-1)+a_+}{2^m} \rfloor]$ has length greater than $\frac{3^n}{2^m} h$, since $a_+ - a_- \geq 4 \cdot 3^n$. If one iterates the interval expansion lemma from an arbitrary starting point $x_0$ that is not a multiple of $3$, one creates a sequence of intervals $[x_{-,k},x_{+,k}]$ of length $\gg (3^n/2^m)^k$ with and midpoint $\alpha_k (3^n/2^m)^k$ for some real numbers $\alpha_k$ that form a Cauchy sequence and thus converge to some limit $\alpha$ as $\alpha \to \infty$, such that every natural number in this interval that is not a multiple of $3$ can be reached by a legal move from $x_0$. Because $\log (3^n/2^m) / \log 2$ is irrational, we see from the equidistribution theorem that $\log ( \alpha (3^n/2^m)^k ) / \log 2$ can be arbitrarily close to an integer, so in particular the interval $[x_{-,k},x_{+,k}]$ will contain a power of two for infinitely many $k$, giving the conjecture (of course, powers of two are not multiples of 3).

The following heuristic argument suggests that the claim should be true for sufficiently large $n,m$ with $3^n/2^m$ close to $1$. In this regime we have $n \approx r \log 2$ and $m \approx r \log 3$ for some large $r$. A legal move of the form $x \mapsto \frac{3^n+a}{2^m}$ can be generated by $n$ applications of $x \mapsto 3x+1$ and $m$ applications of $x \mapsto x/2$, in any order; so there are $\binom{n+m}{m}$ ways to generate a legal move, which by Stirling's formula is
$$ \approx \exp( r (\log 6 \log\log 6 - \log 2 \log\log 2 - \log 3 \log\log 3) ) \approx \exp(1.196 r)$$
up to lower order terms. On the other hand, a calculation using the law of large numbers suggests that the typical size of the offset $a$ is
$$\approx 3^n \approx 2^m \approx \exp( r \log 2 \log 3 ) \approx \exp(0.762 r),$$
again ignoring lower order terms (indeed, I would expect $a$ to have a roughly log-normal distribution around a quantity of this magnitude, and obey a Benford law, in the spirit of this paper of Lagarias and Soundararajan.).
Thus for $r$ large there are significantly more legal moves than likely offsets $a$, and the only obvious restriction on the offset $a$ is that they are not multiples of three. Standard heuristics (based on the coupon collector problem) then suggest that the claim should hold for $r$ large enough.

I ran some numerics but the intervals I found fell a bit short of the claim. For instance, when $n=7$ and $m=9$ (so one considers legal moves of the form $x \mapsto \frac{2187x+a}{512}$) I could find an interval of length 134, but no longer, in which every shift $a$ in this interval that was not a multiple of 3 gave a legal move. There are several lower order terms in the analysis (including a log factor arising from coupon collector problem) that may require one to take $r$ to be relatively large in order to create the intervals of the length required in the claim, given that the difference between the two rates of exponential growth in the heuristc analysis is somewhat slight.

p.s. One consequence of either the original or relaxed Collatz conjecture is that one can reach $1$ from any starting natural number $x_0$ by multiplying by ratios of natural numbers and their Collatz iterates. This weaker claim is in fact a theorem, due to Applegate and Lagarias.

**UPDATE**: Unfortunately the same counterexample of $-1$ that blocked the previous approach, blocks this approach also. A variant of the expansion lemma analysis reveals that after applying $n$ copies of $x \mapsto 3x+1$ and $m$ copies of $x \mapsto x/2$ starting from $-1$, one should be able to reach $\lfloor \frac{-3^n+a_+}{2^m} \rfloor$ (if it isn't a multiple of 3) or $\lfloor \frac{-3^n+a_+}{2^m} \rfloor - 1$ (otherwise); but $-1$ can only iterate to negative numbers, hence $a_+ < 3^n + 2^m \leq 2 \cdot 3^n$. Since $a_-$ is positive, this prevents the interval $[a_-,a_+]$ being of length $4 \cdot 3^n$ as desired. So that was somewhat disappointing; still, I'll leave my two answers up on this question in case it is helpful for some future attempt at this problem. It is interesting that while the problem is posed for positive numbers, the negative counterexample -1 to the conjecture (and its relatives) are somehow lurking behind the scenes to sabotage a number of otherwise viable attacks.

6more comments