# A complementary of the Collatz $3x+1$ problem

Let $$\mathbb{N}_{\text{odd}}$$ be the set of odd positive integers. For $$x_0 \in \mathbb{N}_{\text{odd}}$$ consider the set-valued sequence $$\{A_n\}_{n=0}^{\infty}$$ defined by the formula

$$A_0 = \{x_0\}, \qquad A_n = \{\delta(3x + 1), \; \delta(3x + 3), \, : \, x \in A_{n-1}\}, \quad n \geq 1,$$

where $$\delta(k)$$ denotes the largest odd factor of the integer $$k$$ (e.g., $$\delta(1) = \delta(2) = \delta(4) = 1$$, $$\delta(3) = \delta(6) = \delta(12) = 3$$, $$\delta(15) = \delta(60) = 15$$, etc). Is it true that

$$A := \bigcup_{n=0}^{\infty} A_n = \mathbb{N}_{\text{odd}}?$$

A variant: Suppose now that $$\mathbb{N}_{\pm 1} := \{x \in \mathbb{N} \,:\, x \equiv \pm1 \ (\text{mod}\; 6)\}$$. For $$x_0 \in \mathbb{N}_{\pm 1}$$, $$x_0 \ne 1$$ consider the set-valued sequence $$\{B_n\}_{n=0}^{\infty}$$ defined by

$$B_0 = \{x_0\}, \qquad B_n = \{\delta(3x - 1), \; \delta(3x + 1) \, : \, x \in B_{n-1}\}, \quad n \geq 1$$ Is it true that

$$B := \bigcup_{n=0}^{\infty} B_n = \mathbb{N}_{\pm 1}?$$

• Hi, and welcome to MO. Why have you included $\delta(3x + 3)$? If there were good reason to do so, it could suggest convergence of $1$ implies convergence of every leaf of the Collatz graph (the multiples of $3$), which is of course equivalent to the conjecture. – user334732 Dec 30 '18 at 20:17

If I'm interpreting your question correctly, your question is equivalent to the Collatz conjecture, which is an open problem.

You've expressed the problem using the numbers $$x\equiv\pm1\pmod6$$ as representatives of $$2^m3^n\cdot x$$ which is equivalent to the conjecture because a) these are the $$5$$-rough numbers, b) every even number leads to an odd number, and c) the multiples of $$3$$ are the leaves of the graph.

So you're asking whether the monoid epimorphism $$f(x)=3x+\text{sign}(x)\cdot2^{\nu_2(x)}\cdot3^{\nu_3(x)}, f:\Bbb N_{\pm1}/{\sim}\to\Bbb N_{\pm1}/{\sim}$$ is eventually constant for all finite subsets of $$\Bbb N_{\pm1}/{\sim}$$, where:

$$a\sim b\iff\exists i\in\Bbb Z:2^i\cdot a=b$$

I'm not sure why you included $$\delta(3x + 3)$$ but since this maps some $$x$$ which is not a multiple of $$3$$ to one which is, I'm certain it's no stronger or weaker than the conjecture itself, because in the conjecture as usually stated, the multiples of $$3$$ are the leaves of the graph, therefore it would be sufficient to prove the conjecture for either the leaves or the non-leaves.

If you had a good reason to include $$\delta(3x + 3)$$, I would be interested to know it.

• I thought of this problem while writing the paper "A Randomized Version of the Collatz 3x+1 Problem " (see arXiv:1503.03658). I feel it is related to Collatz, but I cannot tell if it is equivalent to Collatz. I called it "complementary of the Collatz" because here we need to show that the produced sequence takes ALL odd numbers (or ALL $\pm 1$ (mod $6$) numbers in the second version), while for the "original" Collatz we want the sequence to take only finitely many distinct values. – vassilis papanicolaou Jan 1 at 19:46