Collatz Conjecture, sufficient to show odd numbers reach $1$?

Question

The famous conjecture:

Let $$ f(n) = \begin{cases} n/2 & \quad \text{if } n \text{ is even}\\ 3n+1 & \quad \text{if } n \text{ is odd}\\ \end{cases} $$ The Collatz Conjecture states that when applying this function repeatedly to any natural number you will eventually reach 1. For example, starting with $10$ we generate the sequence $$ \{ 10,5,16,8,4,2,1 \} $$

Considering a popular approach to a proof where we want to eliminate sets of natural numbers that reach $1$ until only the empty set remains,

Is it true that you need only show all odd numbers reach $1$?

My reasoning is that if your current number $n$ is even, then either

• it is twice an odd number, or
• dividing by $2$ repeatedly will either
  • reach an odd number greater than $1$ or
  • $n$ is a power of $2$ that will approach $1$ directly

I think then that the question of $n$ reaching $1$ can be reduced to the question of that first odd factor of $n$ reaching $1$.

Probably there are stronger statements that would cover this.

Answer 1

You're right, if you show the conjecture holds true for odd numbers, then you're basically done by your logic. Similarly, you could just prove it for even numbers.

However, it boggles the mind how this would simplify the proof of the full conjecture, considering that for any odd number, the next step in the Collatz iteration gets you to an even number. In other words, you can't really escape not considering even numbers.

If you're interested in reducing the Collatz conjecture, perhaps you'd be interested in the following. You really "just" need to show that

1) There are no cycles.

2) No number escapes to infinity.

Answer 2

To prove the Collatz conjecture, it is sufficient to show that all odd starting numbers converge.

Proof:

Assume there exists a starting number which has a Collatz sequence that diverges (does not terminate to $1$). Then, there must be a smallest starting number $m$ whose Collatz sequence diverges. If this number $m$ is even, on the first iteration, we would have $m/2 < m$. Since $m/2$ has a converging Collatz sequence, it follows that $m$ must be odd.

Answer 3

It's a known fact that to prove for either the even numbers or the odd numbers proves the conjecture. The proof is simpler than you argue. Every odd number leads to an even number and every even number leads to an odd number. Therefore prove for one parity and it follows that every number must either be proven or must lead to a number which is proven, and therefore is itself proven too.

Although that is basically your argument distilled down a little.

There are many ways to potentially prove this, none yet completed. But some method proving only for odd numbers is an acceptable one.

Alex's statement of proving no cycles and no sequence that leads to infinity is also a valid method, and it is also valid to combine the two so e.g. you can ignore the even numbers and analyse the sequences of odd numbers. If you were to prove that no odd number can lead back to itself and no odd number sits on a sequence that leads to infinity, that would also be a proof.

Answer 4

To get what you ask you have to modify the sequence to always get odd numbers, this could be an alternative:

define the following function

$f(n) = \begin{cases} \frac {3 \cdot n +1}{2^{2 \cdot a}} \quad\quad\quad\quad \quad \text{ if } \quad n\equiv \frac {2^{2 \cdot a} -1}{3} \pmod{2^{2 \cdot a+1}} \quad \text{ with }\quad a\geq 1 \\ \frac {3 \cdot n +1}{2^{2 \cdot a+1}} \quad\quad\quad\quad \quad \text{ if } \quad n\equiv \frac {5 \cdot 2^{2 \cdot a+1} -1}{3} \pmod{2^{2 \cdot a+2}} \quad \text{ with }\quad a\geq 1\\ 3^{a} \cdot \frac {n+1}{2^{ a}}-1 \quad \quad \text{if } \quad n\equiv 2^{a+1} -1 \pmod{2^{ a+2}} \quad \text{ with }\quad a\geq 1\\ \end{cases}$

and consider this sequence to get odd $a_i$

$a_i = \begin{cases} \frac {n}{2^{a}} \quad \quad\quad \quad \text{ for } \quad i=0 \quad \text{ and } \quad n\equiv 0\pmod{2^{ a}} \quad \text{ with }\quad a \geq 0 \quad \text{ and } \quad n \not \equiv 0\pmod{2^{ a+1}}\\ f(a_{i-1}) \quad \quad \text{ for } \quad i >0 \end{cases}$

Answer 5

Ignoring evens seems sane given the problem. If you have an even, your number must be reduced by a factor of two, eventually ending at at odd which would start the upward trend.

Given that, we can safely say should an exception be found, it would be an odd number as evens can only provide two results.

1. Eventually factoring to 1.
2. Eventually factoring to an ODD which is lesser than itself.