Question

Question about the Collatz Conjecture

Answer 1

There are broadly two options:
 

1. If we run it for a while and end up repeating a number (other than 1, 2, or 4), we're done - once you've hit a loop, you'll stay in that loop forever.
2. Show that its sequence (or some subsequence of it) is bounded below by some other sequence that stays above 4.

Answer 2

This is a rabbit hole I would avoid anyday

Answer 3

I don't have a real example, obviously, but there are a few possible ways this could be done:

* Show it ends in a loop other than 4,2,1, as mentioned
* Show that it has a repeating pattern of operations that makes it keep growing. As an example, if you can show that you'll get x -> ... -> 3 x -> ... -> 9 x  -> ... -> 27 x and so on forever, then you know x is a counterexample to the conjecture.
* Show it has some property which won't go away under the steps of the Collatz conjecture, and show that 4,2,1 don't have this property.
* Show that it has some property which will make it (after an unknown number of steps) go to a larger number with the same property.

As a (trivial) example, consider "if the number is odd then add 2, if the number is even but larger than 0 then subtract 2, if it's 0 then don't change it". If you start with 1 it's immediately obvious that you will never reach 0 with it. You can formally prove this by showing that 1 is odd, 0 is even, and the transformation never changes an odd number to an even number.

Answer 4

The fact we might not know if a sequence is a counterexample or not is why there is a possibility that the conjecture is independent from ZFC.

It is known that generalized version of Collatz conjecture are undecidable. Therefore, there exist some variants of the conjecture that is independent from ZFC. Whether it's the Collatz conjecture itself that is independent, we don't know.

Answer 5

Let x be a positive integer which the Collatz map C does not iterate to 1. The first thing to note is that there are actually *two* ways in which  C can fail to send x to 1.


a) **x is a pre-periodic point** - Applying C to x, you eventually iterate x to some integer n ≠ 1,2,4 which is a periodic point of C.

b) **x is a divergent point** - The sequence of iterates x, C(x), C(C(x)), ... tends to ∞.


It can be shown without too much difficulty that (a) is equivalent to x being expressible as:

(sum of products of powers of 2 and 3) ÷ (2^m - 3^n)

for some integers m,n≥1.

This can be rewritten as an exponential diophantine equation. There is a direct correspondence between solutions of this diophantine equation and periodic points of Collatz.

As for (b), it can, theoretically, be verified using some non-archimedean analysis. A sufficient (and, conjecturally, *necessary*) condition for x to be a divergent point is the existence of a certain measure zero set of 'irrational' 2-adic integers which is invariant under the left-digit-shift operation.

Answer 6

simple answer is we don't know yet

5n+1 version seem to diverge  
no proofs yet