Proof of Collatz conjecture?

Question

I was "playing" on Project Euler and passed across the Collatz Problem, and it mentioned it was still unproven.

I immediately noticed two things:

• After the $3n+1$ the result is always even, leading to $\frac{n}{2}$
• $\frac{n}{2}$ is an trivial action, especially in a binary representation.

The first optimization that can be done is combining the $3n+1$ step with $\frac{n}{2}$.

$\frac{3n+1}{2} = 1.5n+0.5 = n+((0.5n)-0.5)+1$

---

Looking at the binary representation, $0.5n$ is simply $n$ bitshifted 1 position to the right.

We now focus on $n$ being an odd positive integer (as even numbers are always $2^x$ of an odd number).

Obtaining $((0.5n)-0.5)$ is easily done with the binary representation of $n$, by bitshifting $n$ to the right, and dropping the least significant bit. (Remember, $n$ is odd.)

---

We know full adders have a well known and well defined behaviour:

$S = A \oplus B \oplus C_{i}$

$C_{o} = majority(A, B, C_{i})$

Doing $n+((0.5n)-0.5)+1$ is implemented using a full adder where the input $B_{i}$ has been connected to $A_{i+1}$

_{Sorry for the confusion, but the $n$ on the in-/outputs is unrelated to the number $n$; it needs to be $i$. I will fix this in the image.}

---

By definition, an odd binary number has always $1$ as the least significant bit, and obviously, a $1$ as the most significant bit. The $A_{i+1}$ input from the adder handling the most significant bit falls outside the $n$, and as a result, $0$.

$C_{0} = 1$

$A_{0} = 1$

$A_{i_{max}} = 1$

$A_{i_{max+1}} = 0$

After a complete run has been done, $\frac{n}{2}$ gets done if applicable, and the new $n$ gets fed to the calculator again.

Note that each time the length of the number grows on the most significant bit side, a "foreign" $0$ gets output to $S_{i_{max}}$.

$S_{i_{max}} = (1 \oplus 0 \oplus C_{i_{max-1}}) \neq C_{i_{max-1}}$

$C_{i_{max}} = majority(1, 0, C_{i_{max-1}}) = C_{i_{max-1}}$

$S_{i_{max}} \neq C_{i_{max}}$

_{(This also implies that $n$ never reaches a value in the form of ${2^x}-1$ after the initial value until it reaches $1$ because of the $0$ passed to the $B$ input for the most significant bit. As the only way not to output a $0$ for $S_{_{[msb]}}$ is to not receive a carry trough $C_{i_{[msb]}}$, which means there is at least an earlier bit with $0$ as value.)}

---

But more importantly, when the first $0$ appears in $A_{1}$ will result in an $0$ to $S_{0}$ making the number even, and shrinking the number itself (by applying $\frac{n}{2}$).

$S_{0} = (1 \oplus 0 \oplus 1) = 0$

$C_{0} = majority(1, 0, 1) = 1$

Now, if it keeps finding an alternating bits of $1$'s and $0$'s, it keeps outputting $0$'s, and keeps the carry on. (This allows you to do $\frac{n}{2}$ several times in a row.)

Only if both $A_{i}$ and $A_{i+1}$ are $1$ again, it will start outputting $1$ on $S$.

If however, it encounters a $O$'s on both $A_{i}$ and $A_{i+1}$, the carry $C_{i}$ will will be output to $S_{i}$, and outputs $A_{i}$ to $S_{i}$ until it encounters a $1$'s on both $A_{i}$ and $A_{i+1}$

$S = (0 \oplus 0 \oplus C_{i-1}) = C_{i-1}$

$C_{i} = majority(0, 0, C_{i-1}) = 0$

$S = (1 \oplus 1 \oplus C_{i-1}) = C_{i-1}$

$C_{i} = majority(1, 1, C_{i-1}) = 1$

---

How does this translate to a proof of Collatz conjecture?

_{Note that I'm a mere programmer with a hobby interest in math problems, so excuse me for the low quality. However, I still think this is able to prove that Collatz conjecture is valid, as the growth of the number has hard limits (how many carries can reach the end), while the shrink has no hard limit (shrinks until a 1 occurs) and the switching is fair and one-way (full adder).}

---

_{Note: my personal truth table for the MSB and LSB}

MSB Ci      MSB
010-0--- -> 011---
010-1--- -> 100---
011-0--- -> 100---
011-1--- -> 101---

   B LSB      Co LSB
---0-01  -> ---0-10 (additional $\frac{n}{2}$ once)
---0-11  -> ---1-01
---1-01  -> ---1-00 (additional $\frac{n}{2}$ multiple times)
---1-11  -> ---1-11

Answer 1

The problem with the Collatz conjecture has to do with the possibility of having long "alternating" chains.

Consider a sequence of numbers a₀, a₁, a₂, ... obtained by applying the Collatz function, starting with some integer a₀. Consider just some element of this sequence, a_n: as you note, if a_n is odd, then a_n+1 = 3a_n+1 is even, so that a_n+2 = (3a_n+1)/2. But then what if a_n+2 is again odd? Well, we'd then have a_n+4 = (3(3a_n+1)/2+1)/2 = (9a_n+3)/4. And if this number is again odd...?

In an "alternating" chain of elements like this, each two steps yields an increase in size by a fraction of more than 3/2, which of course is an exponential growth rate. One could say that the problem of the Collatz conjecture is to bound how long these alternating chains can be (and how close together they can be).

Answer 2

To start, I must apologise for not making this more formal.

I'm not entirely certain of what you're saying, but I think I get the gist of it - if so, it looks very similar to an idea I had a few months ago.

Just to confirm we're thinking along the same lines, an odd number n can be expressed as $(1,a_1,a_2,...a_r)$ which becomes $(0,b_1,b_2,...b_s)$ after 1 iteration of the collatz operation, and then $(b_1,b_2,...b_s)$ after the next operation.

if we were to continue on like this, it's easy to see that the the first $r+1$ terms 'disappear' after $2r+2$ terms at most. However, we haven't looked at the elements that are being produced at the 'end'.

I think you were talking about these when talking about the $s_i$ etc. I don't quite follow what you meant by always generating 0's...

if a string ends in $(...,1,0,1)$ it becomes

$(...,1,1,1,1)$ (example, $(1,0,0,0,1,0,1)\rightarrow (0,0,1,0,1,1,1,1)$)
or
$(...,0,0,0,0,1)$ (example, $(1,0,1)\rightarrow (0,0,0,0,1)$)
or
$(...,1,0,0,0,1)$ (example, $(1,1,0,1)\rightarrow (0,1,0,0,0,1)$)

So if your binary representation of n ends in $(1,0,1)$ and has $r+1$ digits, then after two iterations of the collatz function it's length could be $r+2$.

Basically, to use a binary representation to prove Collatz will require showing that all 8 of the possible 3-digit endings of the string generate a new sequence that collapses 'quickly' after the first $2r+2$ iterations. (in other words, the number you're left with after $2r+2$ iterations has length s and collapses down to $(0,0,...,0,1)$ in under $2s+2$ iterations).

Please note this last paragraph is a suspicion of mine, I haven't yet attempted to prove it as I don't like this approach. Apart from any silly mistakes, the rest of the answer is fairly logical and quite simple to show to be true.

Answer 3

I've been exploring this problem without success, but came up with a related problem that might help. Consider the fraction:

(4*4*4 + 4*4*3 + 4*3*3 + 3*3*3) / (4*4*4*4 - 3*3*3*3)

which evaluates to 1. This discussion applies to the entire sequence of such fractions; here's the next one:

(4*4*4*4 + 4*4*4*3 + 4*4*3*3 + 4*3*3*3 + 3*3*3*3) / (4*4*4*4*4 - 3*3*3*3*3)

It's pretty easy to prove (induction works nicely) that these fractions all evaluate to 1.

Now, let's replace the 4's with variables, like so:

(a*b*c*d + a*b*c*3 + a*b*3*3 + a*3*3*3 + 3*3*3*3) / (a*b*c*d*e - 3*3*3*3*3)

The variables are required to be powers of 2 (at least 2). Question: Can we make the fraction evaluate to a positive integer? We already know that setting all the variables to 4 will deliver 1. But can any other positive integer be obtained?

It turns out to be fairly easy to prove that if none of the variables are 2, and any of them are greater than 4, then the fraction lies between 0 and 1. So that leaves just this: What happens if one or more of the variables have the value 2? You can get some negative numbers, but we don't care about those. But you can also get some positive numbers greater than 1... they don't appear to be integers; but how do we know they can't be?

If you can prove there are no positive integer solutions to this fraction (other than 1), I'm pretty sure you've proven the Collatz conjecture. The problems are analogous.