# Prove that an odd Collatz sequence will at some point have two consecutive even numbers

Is there an existent proof for this? It would be an important step to proving the conjecture in any case.

-
What do you mean by an "odd Collatz sequence"? –  Robert Israel Jul 6 '12 at 23:22
In general the initial behavior of any Collatz sequence is a function of the lowest-order bits of the starting number. At least the first $n$ steps are determined by the lowest $n$ bits. So whether any particular length-$n$ string of evens and odds ever occurs is decidable, and can be ascertained by checking $O^{*}(2^{n})$ starting values. –  mjqxxxx Jul 6 '12 at 23:29
Note that if you include negative Collatz sequences, $-1 \rightarrow -2 \rightarrow -1$ is a counterexample. –  Logan Maingi Jul 6 '12 at 23:44

Write the initial odd number in binary notation. The binary representation ends with a number of 1s, preceded by a 0 -- say 'abcd01111'. Now imagine computing two steps ahead in the sequence to $\frac{2x+x+1}{2}$ in binary:

   abcd01111
+ abcd011110
+          1
------------
opqrs01110  divided by 2 is opqrs0111


When the carries have settled you find that this next step has one less digit 1 at the end. Proceed by induction; after finitely many steps you have used up all of the 1s, and the $\frac{2x+x+1}{2}$ is actually even:

   abcd01
+ abcd010
+       1
---------
opqrs00  divided by 2 is opqrs0


at which point two consecutive halvings will happen.

(This could all have been written in a more mathematically dignified form by observing that for every $n\in\mathbb N$ there is exactly one $k\ge 0$ such that $n\equiv 2^k-1 \pmod{2^{k+1}}$. If $k>0$, then the next step in the sequence will be $2^{k+1}+2^k-2\equiv 2(2^{k-1}-1) \pmod{2^k+1}$ and the one after that is $2^{k-1}-1\pmod{2^k}$ -- in other words the two steps have made $k$ decrease by one. But that is not as instructive a way to phrase it, I think).

This argument also implies that the ratio between the starting number and maximum number in the sequence can be arbitrarily large.

-

Start with the odd number $a_1$. Let $e$ be the largest exponent such that $a_1\equiv -1\pmod{2^e}$. Then $a_1\equiv 2^e-1\pmod{2^{e+1}}$. We prove the result by induction on $e$.

If $e=1$, then $a_1\equiv 1\pmod{4}$. It follows that $3a_1+1\equiv 0\pmod{4}$, so we immediately get two consecutive evens.

For the induction step, suppose the result holds when $e=k-1$. We show that the result holds for $e=k$. So suppose that $a_1\equiv 2^{k}-1 \pmod{2^{k+1}}$.

After one round of the $3n+1$ process, we reach $a_2$, where $$a_2\equiv 3(2^k-1)+1\equiv 2^k-2\pmod{2^{k+1}}.$$ After the division by $2$, we get $a_3$, where $$a_3\equiv 2^{k-1}-1 \pmod{2^k}.$$ By the induction hypothesis, the Collatz sequence that starts with $a_3$ contains two consecutive evens, and hence so does the Collatz sequence that starts with $a_1$.

-
One could also prove it without induction, but its quite the same as your proof. Since every positive integer can be written in the form $n_1=a\cdot2^k+2^{k-1}-1$ on exactly one way, you can cipher out a few Collatz terms: $n_2=3a\cdot2^k+3\cdot2^{k-1}-2$, $n_3=3a\cdot2^{k-1}+3\cdot2^{k-2}-1$, $n_4=3^2a\cdot2^{k-1}+3^2\cdot2^{k-2}-2$, and so on: $n_{2x+1}=3^xa\cdot2^{k-x}+3^x\cdot2^{k-x-1}-1$. So finally $n_{2k-2}$ and $n_{2k-1}$ are both even. This also shows where you can expect the two consecutive evens somewhere. –  barto Dec 12 '12 at 15:57