Collatz Conjecture

  • Thread starter phyti
  • Start date
  • #1
441
8

Main Question or Discussion Point

The paper at this site "http://uts.awardspace.info" [Broken] looked interesting to me, but would
anyone else familiar with this problem, it's been around since the 30's, check it out and give an opinion.
 
Last edited by a moderator:

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,820
0
The first mistake I saw was on page 2: "The product 2y obviously takes the form 3n+1", which is tantamount (in this problem) to assuming that all odd integers are 1 mod 6.

The statement (also on p. 2) that "each {x} is unique for each y" has the obvious counterexample y = 5, for which x = 3, 13, 53, ... are possible. In fact finding counterexamples is easy because there are so many.
 
Last edited:
  • #3
gel
533
5
Wouldn't normally read such a paper, but as it's so short - here goes. First, a couple of comments on CRGreathouses comments above...

The first mistake I saw was on page 2: "The product 2y obviously takes the form 3n+1", which is tantamount (in this problem) to assuming that all odd integers are 1 mod 6.
It's not very clearly written, so I can't be sure what he *really* means by many of his sentences. However, here I think he is only considering the case where y is 5 mod 6, so it looks right.

The statement (also on p. 2) that "each {x} is unique for each y" has the obvious counterexample y = 5, for which x = 3, 13, 53, ... are possible. In fact finding counterexamples is easy because there are so many.
Yeah, that's just wrong. However, he never tries to use this (wrong) fact and it is clear that he knows you have to make a choice from an infinite set of possibilities.
In fact, he even shows that each term in such a sequence is 4 times its predecessor plus one.
I think he meant to say that y is unique for each x, which is obvious.

Looks like the main error in his reasoning is in the very last line.

All complete and incomplete reverse sequences can be formed using these sets.
Therefore all forward sequences will terminate with 1.
He only ever considers reverse sequences starting from 1. Clearly when you "un-reverse" such a sequence it will end in 1.
If he wanted to show that every sequence ends in 1, then he would need to show that every number appears in some reverse sequence starting from 1, which he never does.
 
  • #4
CRGreathouse
Science Advisor
Homework Helper
2,820
0
It's not very clearly written, so I can't be sure what he *really* means by many of his sentences. However, here I think he is only considering the case where y is 5 mod 6, so it looks right.
I don't think so. That's the part in the paper in which the author assumes (*with* loss of generality) that 3n+1 is of the form 2^a * (6b + 1).
 
  • #5
27
0
My friend has been working on this.. but I highly doubt he will make much progress in solving it.

Erdos did not think mathematics was ready for such problems. He also called it one of the few remaining problems which can readily explained to the layman. I think he offered a 50 dollar reward for its proof, which is still available through his estate.
 
  • #6
CRGreathouse
Science Advisor
Homework Helper
2,820
0
My friend has been working on this.. but I highly doubt he will make much progress in solving it.

Erdos did not think mathematics was ready for such problems. He also called it one of the few remaining problems which can readily explained to the layman. I think he offered a 50 dollar reward for its proof, which is still available through his estate.
Erdos offered $500. I though the prizes were being supported by Ron Graham rather than through the Erdos estate...?

I hope your friend bothers to read the literature on the problem before putting in too much work. For example, I see that Lagarias (1985, using a result due to Crandall and calculations due to Yoneda) showed a lower bound of 275,000 for the length of any nontrivial cycle.

I believe Lagarias was mistaken in his calculation, but on the conservative side. He used [itex]q_{13}=190737[/itex] instead of [itex]q_{13}=190537[/itex] but somehow managed to give 275,000 instead of 285,000 (even though the error should have gone in the other direction!).

Reworking the Crandall formula with Tomás Oliveira e Silva's calculations (no cycles up to 19 * 258) and an optimal j (20 in this case rather than 13) I come up with a far better lower bound: 1,285,930,588. Not to brag, but this beats Wikipedia's claim by better than 35,000-fold!
 
  • #7
441
8
I revisited the site named in post 1, and the paper has been revised and is now a proof.
In studying it, I can't find any errors, but that's just one opinion.
 
  • #8
CRGreathouse
Science Advisor
Homework Helper
2,820
0
I revisited the site named in post 1, and the paper has been revised and is now a proof.
In studying it, I can't find any errors, but that's just one opinion.
I'm curious: how did you come across this paper?
 
  • #9
26
0
Are there any flaws in this approach?

Iff n ≡0(MOD2) then n will be divided by 2 any number of times until an odd number, m1, is obtained. Iff n ≡19MOD2) let n=m1.
Iff m1≡1(MOD4) then 3m1+1≡0(MOD4). Let 3m1+1=a, then either a/2 ≡2(MOD4) or a/2 ≡0(MOD4). In the latter case, either a/2 ≡2(MOD4) or a/2 ≡0(MOD4) and successive divisions by 2 will yield a number ≡2(MOD4). Another halving will give an answer m2≡1(MOD4), and the process is repeated. Since 3mn+1 is always a multiple of 4, mn+1=(3mn+1)/(4*2r), where r>/=0. Therefore, if mn>1 then mn+1<mn. Then each term is less than the previous, and because no term can be <1, the result must converge to 1.
Iff m1≡3(MOD4) then 3m1+1≡2(MOD4) and a/2 ≡1(MOD4), and from there the argument continues as in the case for m1≡1(MOD4).
 
  • #10
26
0
In the previous post I forgot to put in the subscripts, which may have caused confusion. I also made a typo with one of the brackets. Here is a better version. I used Gauss's congruences in my attempt.

Iff n ≡0(MOD2) then n will be divided by 2 any number of times until an odd number, m[/1SUB], is obtained. Iff n ≡1(MOD2) let n=m[/1SUB].

Iff m[/1SUB]≡1(MOD4) then 3m[/1SUB]+1≡0(MOD4). Let 3m[/1SUB]+1=a, then either a/2 ≡2(MOD4) or a/2 ≡0(MOD4). In the latter case, either a/2 ≡2(MOD4) or a/2 ≡0(MOD4) and successive divisions by 2 will yield a number ≡2(MOD4). Another halving will give an answer m[/2SUB]≡1(MOD4), and the process is repeated. Since 3m[/nSUB]+1 is always a multiple of 4, m[/n+1SUB]=(3m[/nSUB]+1)/(4*2r), where r>/=0. Therefore, if [/nSUB]>1 then m[n+1/SUB]<m[/nSUB]. Then each term is less than the previous, and because no term can be <1, the result must converge to 1.

Iff m[/1SUB]≡3(MOD4) then 3m[/1SUB]+1≡2(MOD4) and a/2 ≡1(MOD4), and from there the argument continues as in the case for[/1SUB] m≡1(MOD4).
 

Related Threads on Collatz Conjecture

Replies
1
Views
3K
  • Last Post
Replies
9
Views
4K
  • Last Post
Replies
2
Views
4K
Replies
5
Views
4K
Replies
2
Views
4K
  • Last Post
Replies
14
Views
5K
Replies
2
Views
5K
Replies
7
Views
2K
Replies
9
Views
9K
  • Last Post
Replies
20
Views
7K
Top