40
$\begingroup$

The Collatz $3x+1$ conjecture claims that any positive integer can eventually be reduced to $1$ by iterative application of the maps $x \mapsto 3x+1$ whenever $x$ is odd and $x \mapsto x/2$ whenever $x$ is even.

While the Collatz conjecture is still open, I wonder if the following relaxed version is any simpler. In this relaxed version we are allowed to apply maps in any order keeping the numbers integer. That is, if $x$ is odd, we still have to apply the $x \mapsto 3x+1$ map; but for even $x$, we have the freedom to choose between $x \mapsto 3x+1$ and $x \mapsto x/2$. The conjecture is that for any positive integer, we can reduce it to $1$ with some iterative sequence of maps.

Clearly, the Collatz conjecture would imply the relaxed version. But it may happen that the relaxed version is much simpler. Is it?

The question is inspired by discussion of the sequence http://oeis.org/A109732 which is a permutation of the odd positive integers iff the relaxed version of the $3x-1$ variant of the Collatz conjecture holds.

UPDATE. The minimum number of iterations to reach $1$ in this relaxed version is given by http://oeis.org/A127885 and this number is often smaller than that for the Collatz conjecture given by http://oeis.org/A006577 .

$\endgroup$
  • 4
    $\begingroup$ It can certainly reduce the time for reducing it to zero by a good amount. For example 27 takes at most 48 steps (out of possibilities considered) instead of 112. $\endgroup$ – wythagoras Sep 3 '15 at 18:24
  • $\begingroup$ If instead of 3x+1 you had ceil(\alpha x + 1) with \alpha smaller than 2, you could show convergence pretty easily. My feeling is that there is a threshold between 2 and 3 where for \alpha below the threshold, it will be easy to prove convergence, and for \alpha above it, it will be hard. Gerhard "The Threshold Might Be Two" Paseman, 2015.09.03 $\endgroup$ – Gerhard Paseman Sep 3 '15 at 18:47
  • 8
    $\begingroup$ @GerhardPaseman: the idea fails for $\alpha=\frac{\sqrt(5)+1}{2}$ (and 7 as starting point) and more generally for salem numbers. See item 29 in the Lagarias's survey on the $3x+1$ problem: arxiv.org/pdf/math/0309224.pdf; for more detail: math.grinnell.edu/~chamberl/papers/3x_survey_eng.pdf $\endgroup$ – Yaakov Baruch Sep 3 '15 at 22:17
  • 3
    $\begingroup$ @wythagoras: In fact, 27 can take just 23 steps (and that's the minimum): 27 -> 82 -> 41 -> 124 -> 373 -> 1120 -> 560 -> 280 -> 140 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1. $\endgroup$ – Max Alekseyev Sep 3 '15 at 23:48
  • $\begingroup$ @YaakovBaruch, I am surprised. I must have been thinking about something different from what I said. Thank you for the links. Gerhard "And It Wasn't Floor Either" Paseman, 2015.09.03 $\endgroup$ – Gerhard Paseman Sep 4 '15 at 0:19
5
$\begingroup$

I'll write $\longrightarrow$ for some standard iterations and $\implies$ for some possibly non-standard iterations. The relaxed Collatz conjecture is that for all $x$, $x \implies 1$. I'll call counterexamples to the conjecture escapees.

First of all, since it's a good example of the notation, a lemma: for all $a$, $4 a \implies 9 a + 1$.

Proof: $4a \implies 12 a + 1 \longrightarrow 36a + 4 \longrightarrow 18a + 2 \longrightarrow 9 a + 1$.

$\square$

Now here is what I will try to show:

Theorem: If $x$ is the smallest escapee, then $4x \implies 1$.

Proof: By elementary considerations, $x \equiv 3 \pmod{4}$. If $x \equiv 2 \pmod{3}$, then $\frac{2 x - 1}{3} \longrightarrow 2 x \longrightarrow x$. So in this case, $2 x$ can't be an escapee, and neither can $4 x$.

The next case is $x \equiv 0 \pmod{3}$. Write $x = 12k+3$. Using the lemma, $4x \implies 27k+7$. Observe that $x > 9k+2 \rightarrow 27k+7$ if $k$ is odd. Now if $x \equiv 15 \pmod{24}$, we also have that $4x \implies 1$.

It's also possible that $x \equiv 3 \pmod{24}$. In that case, we have $x = 24 j + 3$ and $x \longrightarrow 27j+4$. This means $j$ cannot be even. So we drill down again, with $x = 48i + 27 \longrightarrow 81i+49$. This means $i$ cannot be odd. But also, $4x = 4(48i+27) \implies 81i + 92$, so if $i$ is even, the next step brings us under $x$. This covers all the $x \equiv 0 \pmod{3}$ cases.

So far, our result is that if $x \implies 4x$, then $x \equiv 7 \pmod{12}$. Now I'll handle that case. Suppose $x \implies 4x$ and $x = 24k + 7$. Then we have:

$4x = 4(24k+7) \implies 9(24k+7)+1 = 216k+64 \longrightarrow 108k+32 \longrightarrow 54k+16$.

But also, $18k+5 \longrightarrow 54k+16$. This means $18k+5$ is an escapee too, but it can't be, since it's less than $x$. So the hypothesis is false and we have $x = 24k + 19$ instead.

Now, consider:

$4x = 4(24k+19) \implies 216k + 172 \longrightarrow 108k + 86 \longrightarrow 54k + 43 \longrightarrow 162k + 130 \longrightarrow 81k+65$.

By similar reasoning, $k \neq 3 \pmod{4}$, or else we can continue the chain two more steps to get an escapee less than $x$. Finally,

$x = 24k+19 \longrightarrow 72k+58 \longrightarrow 36k + 29 \longrightarrow 108k + 88 \longrightarrow 54k + 44 \longrightarrow 27k + 22$.

shows that $k$ can't be even, and substituting $k = 4 j + 1$:

$27k + 22 = 108j + 49 \longrightarrow 324j + 148 \longrightarrow 162j + 74 \longrightarrow 81j + 37 < x$

completes the proof, since that's all the cases.

$\square$

Corollary: if the Collatz conjecture is false and the smallest counterexample leads back to itself then that number is not a counterexample to the relaxed Collatz conjecture. In other words, if $y$ is the smallest number satisfying $\neg(y \longrightarrow 1)$, then $y \longrightarrow y$ implies $y \implies 1$. This is a weaker version of what I originally thought I had proved.

Corollary: If $4x$ is an escapee, then there is an escapee smaller than $x$. This suggests to me a recursive descent strategy where we attempt to show $z \implies 4k < 4x$. But it's not clear if number-crunching will get us anywhere further.

$\endgroup$
  • $\begingroup$ Erm... "It ends in a finite cycle" is not the same as "it returns to the original number" Am I missing something? $\endgroup$ – fedja Dec 15 '17 at 16:15

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.