Take the 2-minute tour ×
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.

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

alt text

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
share|improve this question
21  
It doesn't. The Collatz conjecture is open for a good reason: it is extremely hard. I don't have to find a flaw in this proof to know that it's not a proof because if it were this easy, somebody would've done it already. When you propose to have solved a well-known open problem, especially without having done any significant work, you are implicitly insulting everybody who has ever worked on the problem by assuming that there is an extremely simple solution that all of those people missed. –  Qiaochu Yuan Jan 2 '11 at 15:29
5  
@alexanderpas: "also, I'm not asking you to write my proof, certainly not! I'm merely asking how this translates to proof." I'm not appreciating the distinction here: could you clarify? Anyway, as I said before, I am a research mathematician and I cannot follow the argument as it is written, not even enough to point to statements as being true and false. –  Pete L. Clark Jan 2 '11 at 17:20
20  
Guys, calm down, calm down. Alex's first language isn't English and he's a math novice, it's understandable that there's going to be a lot of confusion reading through his work. What's more important is figuring out what he wants from this question. As far as I figure, by "translate" he means to help him switch his pseudo-proof into actual proof notation, not to verify whether or not the proof is correct. This site's supposed to be for mathematicians at any level. Alex didn't mean any harm and claiming that he's insulting you won't do anything but give off a bad impression of the community. –  Mana Jan 2 '11 at 18:02
26  
@Pete, Qiaochu: Remember Sylvester-Gallai prolem? The problem was open for at least 30 years before we got an amazingly simple proof (if I recollect correctly). IMO, The problem here is that the OP expects us to do the bulk of his work for him. Currently what is written is an incoherent mess. That is what we need to be addressing, rather than claiming impossibility of a simple proof. Once OP makes it coherent, I expect it should be much easier to find the flaws. If OP does not make any attempts, I believe we can close it as Not a Real Question. Just my 2c. –  Aryabhata Jan 2 '11 at 19:01
1  
@Moron: I agree with you. Note that I never said that it was impossible that there could be a short, easy proof of a famous theorem. (It's merely unlikely, but the unlikely does occur occasionally -- by definition?) My point is the same as yours: the OP claims to have a proof of a big conjecture, but what he has written is completely incoherent. As a personal reaction, I find this annoying. –  Pete L. Clark Jan 2 '11 at 19:26
show 5 more comments

3 Answers 3

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

Consider a sequence of numbers a0, a1, a2, ... obtained by applying the Collatz function, starting with some integer a0. Consider just some element of this sequence, an: as you note, if an is odd, then an+1 = 3an+1 is even, so that an+2 = (3an+1)/2. But then what if an+2 is again odd? Well, we'd then have an+4 = (3(3an+1)/2+1)/2 = (9an+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).

share|improve this answer
    
Yes, I considered such possibility, and came to the conclusion that the worst case scenario for this is an number of the $2^x-1$ form. (coincidentally, also the worst you can feed to the string of full adders) HOWEVER, the forced introduction of a foreign $0$ upon expanding via $B_{_{[MSB]}}$ in combination with the full adder behaviour $S=(1 \oplus B \oplus 1)=B$ causes the length of the "problem making" string of ones to decrease, until the foreign 0 has reached the least significant bit -- I've added a truth table for the MSB and LSB to the original post. –  alexanderpas Jan 2 '11 at 16:18
5  
I don't know whether the longest alternating chain occurs for $2^n - 1$; but that's not the only problem. If you encountered e.g. multiple alternating chains of length 10, each ending with an odd multiple of 4 and leading to another alternating chain of length 10, you would still get exponential growth each iteration (by 1.89 for each such chain). Bounding the length of an individual chain is not enough; you have to show that in any sequence, you get on average longer descending chains than alternating chains, and by a large enough margin. –  Niel de Beaudrap Jan 2 '11 at 17:36
1  
@alexanderpas: Could you explain how you came to that conclusion? (meaning: Not how you convinced yourself, but how you know it is true.) –  Andres Caicedo Jan 2 '11 at 21:12
    
@Andres it requires the $0$ that breaks the alternating chain to come from the farthest possible position in the number, while any other odd number has $0$ earlier in the number, which, thanks to the functionality of the full adder, will reach the start of the number earlier. Specifically the defined full adder behaviour $S = A \oplus B \oplus C_{i}$ for each bit. (what did I do? ;)) –  alexanderpas Jan 2 '11 at 23:09
3  
In exactly what sense are numbers of the form $2^x-1$ the "worst case scenario"? Consider 31911 vs. 32767. –  mhum Jan 4 '11 at 2:12
show 1 more comment

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.

share|improve this answer
add comment

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.

share|improve this answer
3  
? Im confused. How does this relate to collatz ? –  mick Oct 11 '12 at 13:33
add comment

Your Answer

 
discard

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.