1
$\begingroup$

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

  • 0
    Note that if you include negative Collatz sequences, $-1 \rightarrow -2 \rightarrow -1$ is a counterexample.2012-07-06

2 Answers 2

4

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.

1

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$.

  • 0
    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.2012-12-12