Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Talk:Collatz conjecture

I have several objections to this section:

<quote>

There is another approach to prove the following conjecture, which considers the bottom-up method of growing Collatz graph. Collatz graph is defined by an inverse function,

$f (n) = {2 n}$ if $n\equiv 0 \pmod{3}$

$f (n) = {2 n,(2 n - 1) / 3}$ if $n\equiv { -1, 1}) \pmod{3}$

Thus looking from this perspective, we have the problem redefined in the following way. The Collatz conjecture states,

The inverse function forms a tree except for the 1-2 loop.
All integers are present in the tree.

</quote>

First of all, it is wrong. It should be

$f (n) = {2 n}$ if $n\equiv { 0, 1} \pmod{3}$

$f (n) = {2 n,(2 n - 1) / 3}$ if $n\equiv { -1} \pmod{3}$

If n=7 then the original rule would have 7 branch to 14 and 13/3 which is not an integer and thus, invalid. The second rule is invoked ONLY when n == 2 (mod 3). Or -1 if you prefer.

Second, it is implied, but not specifically stated, that the rules that are being inverted are not the same as given in the top of the article. This inverse tree modifies the odd number rule to be (3n+1)/2. This modification changes the sequence to

3 -> 5 -> 8 -> 4 -> 2 -> 1 -> 2 -> 1 ...

Whereas the sequence under the original 3x+1 rule is

3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 ...

From the modified rule, you get a "V" tree:

 32 10 3
 |  | /
 |  |/
 16 5
 | /
 |/
 8
 |
 |
 4  [1]
 | /
 |/
 2
 |
 |
 [1]

The original rule produces an "inverted L" tree:

 32 10__3
 |  |
 |  |
 16_5
 |
 |
 8
 |
 |
 4__[1]
 |
 |
 2
 |
 |
 [1]

Generating an "inverted L" tree is a bit trickier, but the rules would be

$f (n) = {2 n}$ if $n\equiv { 0, 1, 2, 3, 5} \pmod{6}$

$f (n) = {2 n,(n - 1) / 3}$ if $n\equiv { 4} \pmod{6}$

Lastly, why is the 1-2 loop not considered part of the tree? And when saying that all numbers are on "the tree", I think it should be specifically pointed out that the conjecture being true implies that there is only one tree. The reason is that there are other systems, such as 3x+5 or 3x+1 with negative numbers, in which case there is more than one tree (and thus the conjecture fails for such systems).

--Mensanator 21:47, 3 Feb 2005 (UTC)

Where is a proof? -- Taku 03:13, Mar 23, 2005 (UTC)

Proof of what? What are you asking about? Proof that the bottom-up method described is wrong? Proof that other systems fail the conjecture? I'll be happy to back up my claims if you tell me what you object to.

--Mensanator 23:27, 25 Mar 2005 (UTC)

Well, by a proof I meant a proof of this conjecture. But sorry, I missed this in the article: "The conjecture has been checked by computer for all start values up to 3 × 2⁵³ = 27,021,597,764,222,976, but a proof of the conjecture has not been found." -- Taku 00:25, Mar 26, 2005 (UTC)

Would somebody double check the recent anon changes?

Thanks. Oleg Alexandrov 23:48, 30 Mar 2005 (UTC)

Last updated: 05-28-2005 22:08:52

Science Fair Project Encyclopedia Contents Page

10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

All Science Fair Projects