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}? $$

  • $\begingroup$ 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. $\endgroup$ – samerivertwice 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.

  • $\begingroup$ 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. $\endgroup$ – vassilis papanicolaou Jan 1 at 19:46

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.