While trying to prove the Collatz conjecture I came across the following Lemma :

Lemma $1$ :

All variables are positive integers.

Define $Collatz(n)$ as the result of the (repeated) collatz iteration $x/2$ for even , $3x+1$ for uneven halt at $1$.

Define $Collatz2(n)$ as the result of the (repeated) iteration $x/2$ for even , $3x+3$ for uneven halt at $3$.

Lemma 1 says for each positive integer $n$ $:$ $Collatz(n) = 1 <=> Collatz2(n) = 3$

How to prove that ?

Edit : $n$ is the starting value for both $Collatz$ and $Collatz2$ , Imho its obvious but it seems it was not clear enough. $x$ is just used to describe the process of the iterations.


Edit : Bonus question ( not related to my attempt at proving Collatz )

On average in a race between $Collatz(n)$ and $Collatz2(n)$ which reaches its halting value( $1$ or $3$) first ( less iterations required = faster ) ?

Too clarify consider the hypothetical example :

We define $f(n) = 1$ if $Collatz$ wins the race and $= 0$ if $Collatz2$ wins the race.

Let $F(n) = f(1) + f(2) + ... + f(n)$.

Then the limit as $n$ goes to infinity of $F(n)/n$ gives for example $\pi/10$.

Edit : related question : What is known about Collatz like 3n + k?

  • 4
    $\begingroup$ Before you try to prove something, you should have some reason to think it's true. What's yours? $\endgroup$ – Gerry Myerson Oct 11 '12 at 12:36
  • 1
    $\begingroup$ @mjqxxxx There is a difference. This is just saying, if one works, then both work. So, it doesn't prove that both work and thus is not guaranteed to be difficult. It's entirely possible there is a very simple proof. $\endgroup$ – GeoffDS Oct 11 '12 at 14:00
  • 1
    $\begingroup$ @ mjqxxxx : equivalence relations and equivalent statements are very foundational in mathematics and occur often for hard intresting problems. As example it is easier to find an equivalent statement to the Riemann Hypothesis than to solve it. Also Lemma 1 as I described it , is not as hard as the Collatz conjecuture in the sense that it is a weaker statement. $\endgroup$ – mick Oct 11 '12 at 14:01
  • 1
    $\begingroup$ A very simple (I think) but thorough (I think as well) work out is at go.helms-net.de/math/collatz/Collatz_3x_r.pdf . Perhaps it might be useful to take the main ideas/formulae into an own answer, but this whole thread is a bit aged to put much effort into, isn't it? $\endgroup$ – Gottfried Helms Mar 7 at 9:39
  • 1
    $\begingroup$ @Gottfried as a fan of tommy1729 and yourself , I was aware of your pdf’s. You have a very interesting website. But I should probably read it again. Thanks for the link. It is useful to me and other readers. $\endgroup$ – mick Mar 7 at 18:58

To explain mercio's answer in greater detail: suppose that $n$ is a number of the form $3k$; then obviously $n$ and $k$ are either both odd or both even. Now, imagine running one step of Collatz2 on $n$: if $n$ is even, then $\mathrm{Collatz2}(n) = n/2 = 3k/2 = 3(k/2) = 3\cdot\mathrm{Collatz}(k)$. Similarly, if $n$ is odd, then $\mathrm{Collatz2}(n) = 3n+3 = 3(3k)+3 = 3(3k+1) = 3\cdot\mathrm{Collatz}(k)$. This means that the sequence of Collatz2 iterates for a number $n=3k$ is exactly the sequence of 'original' Collatz iterates for $k$, multiplied by $3$.

Now, suppose that we have some odd $n$ (if $n$ is even, then obviously we can divide out all the factors of 2 and eventually get an odd starting point); then the first Collatz2 step takes us to $3n+3$ — but this is a number of the form $3k$ (with $k=n+1$), and so now everything in the first paragraph applies. This means that for $n$ odd running Collatz2($n$) is exactly like running Collatz($n+1)$ — this is why you see Collatz2($31$) converging so quickly, because it's identical to running Collatz($32$).

At heart, this means that there's nothing to be gained by studying Collatz2, but there's nothing to be lost either; it is exactly equivalent to the original Collatz problem.

One further point that bears raising, though, is your Lemma 1: 'for all positive integers $n$, $\mathrm{Collatz}(n) \Leftrightarrow \mathrm{Collatz2}(n)$'. As it's stated, this is precisely equivalent to the Collatz conjecture itself - but this is a different statement from one saying that 'Collatz($n$) is true for all positive integers $n$ if and only off Collatz2($n$) is true for all positive integers $n$'. To see why, consider replacing Collatz($n$) with '$n$ is even' and Collatz2($n$) with '$n$ is odd'; then 'all positive integers are even if and only if all positive integers are odd' is true (since both sides are false!), but 'for all positive integers $n$, $n$ is even if and only if $n$ is odd' is false. Universal quantification (the 'for all' statement) doesn't distribute over 'if and only if' in the way that you're using here.

ADDED: To see how Lemma 1 implies the Collatz conjecture, we start by breaking down into cases. (For convenience here, I'm going to abbreviate 'the Collatz sequence starting from $n$ converges' as $C(n)$ and 'the Collatz2 sequence starting from $n$ converges' as $C_2(n)$.) First, if $n$ is even, then our first step of Collatz takes us to $n/2$, and so (almost trivially) $C(n)\Leftrightarrow C(n/2)$, and in particular $C(n/2)\Rightarrow C(n)$. On the other hand, if $n$ is odd, then we use our lemma: we know that $C_2(n)\Leftrightarrow C(n+1)$ by the equivalence shown above, and the lemma states that $C(n)\Leftrightarrow C_2(n)$; putting the two together, we get $C(n)\Leftrightarrow C(n+1)$. But since $n+1$ is even (because we're looking at the $n$ odd case), $C(n+1)\Leftrightarrow C((n+1)/2)$, so we have the equivalency $C(n)\Leftrightarrow C((n+1)/2)$ and in particular $C((n+1)/2)\Rightarrow C(n)$. Now we can induct, using the strong induction principle: suppose we have $\forall k\lt n C(k)$. Then by specializing we have (either) $C(n/2)$ or $C((n+1)/2)$; therefore $C(n)$ by (one of) the two implications we proved. Therefore, $(\forall k\lt n C(k))\Rightarrow C(n)$, and since we know $C(1)$ we get $\forall n C(n)$.

| cite | improve this answer | |
  • $\begingroup$ Thanks for the answer Steven. But I did miss your 'further point' .. $\endgroup$ – mick Oct 11 '12 at 16:27
  • $\begingroup$ The statement $\forall{n}C_1(n) \equiv \forall{n}C_2(n)$ is true (as shown here). It is weaker than @mick's original lemma: $\forall{n}(C_1(n)\equiv C_2(n))$. That lemma is true if the Collatz conjecture is true, but the converse isn't obvious. $\endgroup$ – mjqxxxx Oct 11 '12 at 16:57
  • $\begingroup$ @ mjqxxx and Steven : Thanks got it. $\endgroup$ – mick Oct 11 '12 at 17:03
  • $\begingroup$ @mjqxxxx I was thinking about expanding this answer with a proof of that converse, actually, showing that the lemma implies the Collatz conjecture - it sounds like it would be worthwhile. $\endgroup$ – Steven Stadnicki Oct 11 '12 at 17:14
  • $\begingroup$ @StevenStadnicki: If the lemma is equivalent to the Collatz conjecture, then that is worth proving (as it doesn't seem obvious). Is it (equivalent, and/or obvious)? $\endgroup$ – mjqxxxx Oct 11 '12 at 17:22

If $n$ is odd, then $3n+3$ is a multiple of $3$, and if $n$ is an even multiple of $3$, $n/2$ is still a multiple of $3$. So unless you happen to pick a number where every term in the sequence is even (which can only happen with $n=0$ but then $n$ is a multiple of $3$ too), you will eventually end up with a sequence containing only multiples of $3$.
And if you look closely, for $n$ even, $3n$ is sent to $3(n/2)$ and for $n$ odd, $3n$ is sent to $3(3n+1)$ so your sequence from $3n$ is simply the normal Collatz sequence starting from $n$ but multiplied by $3$.

You can think of the Collatz2 sequences as Collatz sequences that are allowed to start from numbers of the form $n/3$. Then those sequence always end up being sequences of integers, i.e. regular Collatz sequences (and conjecturally end up at $1$). There is no new branch in the Collatz graph if you add all the $n/3$ numbers.

| cite | improve this answer | |
  • $\begingroup$ Im sorry but I think I misunderstood or disagree. Let $n$ be 31. Then Collatz iteration of 31 goes up to 890 and takes many steps to arrive at 1 whereas Collatz 2 goes to 3 rapidly without taking high values. The ratio of 3 seems to small : inconsistant with iteration length and values. $\endgroup$ – mick Oct 11 '12 at 15:00
  • $\begingroup$ A better example $n$ = 25. For collatz we multiplied by 3 7 times before we reached 1. But for collatz2 we multiplied by 3 only 3 times before we reached 3. 3 and 7 are relatively prime so I do not see such a simple connection. Certainly not some sort of 3 ratio ? $\endgroup$ – mick Oct 11 '12 at 15:16
  • $\begingroup$ The same problem occurs when we divide by 2 and count that. $\endgroup$ – mick Oct 11 '12 at 15:17
  • $\begingroup$ @mick I think you misunderstand mercio's point. It is not that you use the same $n$; it's that there is an isomorphism between the two problems - that is to say, for every $n$ there is an $m$ such that starting the Collatz2 sequence at $n$ is equivalent to starting the Collatz sequence at $m$. If you start with $n=31$, then your $m=32$; that is, running Collatz2 from $n=31$ is equivalent to running 'original' Collatz from $m=32$. $\endgroup$ – Steven Stadnicki Oct 11 '12 at 15:43
  • $\begingroup$ So if Collatz is true then your conjecture is true: 'for all $n$, Collatz($n$) converges' is true, so 'for all $m$, Collatz2($m$) converges' is also true, and so the equivalence 'for all $n$, Collatz($n$) converges iff Collatz2($n$) converges' is correct because both sides are simply true. $\endgroup$ – Steven Stadnicki Oct 11 '12 at 15:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.