Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 4 down vote accepted

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:

+ 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:

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

share|cite|improve this answer

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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