Is there an existent proof for this? It would be an important step to proving the conjecture in any case.
Prove that an odd Collatz sequence will at some point have two consecutive even numbers
-
0Note that if you include negative Collatz sequences, $-1 \rightarrow -2 \rightarrow -1$ is a counterexample. – 2012-07-06
2 Answers
Write the initial odd number in binary notation. The binary representation ends with a number of 1
s, 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 1
s, 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$.
-
0One 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. – 2012-12-12