Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Collatz Conjecture

  1. Aug 26, 2008 #1
    The paper at this site "http://uts.awardspace.info" 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.
     
  2. jcsd
  3. Aug 27, 2008 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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: Aug 27, 2008
  4. Aug 27, 2008 #3

    gel

    User Avatar

    Wouldn't normally read such a paper, but as it's so short - here goes. First, a couple of comments on CRGreathouses comments above...

    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.

    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.

    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.
     
  5. Aug 28, 2008 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  6. Sep 13, 2008 #5
    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.
     
  7. Sep 14, 2008 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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!
     
  8. Sep 14, 2008 #7
    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.
     
  9. Sep 14, 2008 #8

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I'm curious: how did you come across this paper?
     
  10. Feb 9, 2011 #9
    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).
     
  11. Feb 11, 2011 #10
    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).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?