Collatz Conjecture

Discussion in 'Physics & Math' started by Absane, Sep 23, 2005.

  1. Absane Rocket Surgeon Valued Senior Member

    Messages:
    8,989
    I am curious, has anyone ever heard of this? Or even better, has anyone here actually tried working on it?

    For those unsure of what I mean.. Pick any postive integer x. If x is odd, multiply it by 3 and add one. If x is even, divide by two. Repeat this. The conjecture states that for any number in Z+ the sequence will end in the cycle 4, 2, 1.
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. Physics Monkey Snow Monkey and Physicist Registered Senior Member

    Messages:
    869
    Absane,

    It is a very interesting problem, so much so that Paul Erdos thought it was beyond the mathematics of his time. He offered one of his famous prizes to anyone who could prove it. I know it has been checked up to pretty high numbers on the computer, and that there are statistical reasons why it is probably true. You may have already known these few tidbits and I don't really know much about it, but maybe someone else can tell you more.
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. Absane Rocket Surgeon Valued Senior Member

    Messages:
    8,989
    I have actually figured out the statistical reasoning out myself. It is funny how simple the problem is to state, even more so than Fermat's Last Theorem... but it seems to be just as hard if not harder.

    I have been working on it on and off since my senior year in high school.. I am now just barely in my Junior year of college. I reduced the problem down to a summation with 2^k and binomial coeficients (you know, the whole factorial thing). Basically 2^k*(n i) + 2^g(p i) etc. If I can show this reduces again to one big 2^m summation, I will have proved it. It requires a lot. I am just wondering if anyone else has suggestions.
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. Rosnet Philomorpher Registered Senior Member

    Messages:
    681
    How much do you know about iterated functions (as in fractals)?
     
  8. Absane Rocket Surgeon Valued Senior Member

    Messages:
    8,989
    Shamefully, very little.
     
  9. Rosnet Philomorpher Registered Senior Member

    Messages:
    681
    You should look it up. I worked on the conjecture for about three days last year. I figured I could use something along the lines of iterated functions. And I'll (you'll) also have to develop some techniques independently. I was learning more interesting stuff last year, and didn't pay much attention to this. But you've probably got me started again.
     
  10. Absane Rocket Surgeon Valued Senior Member

    Messages:
    8,989
    Why only 3 days?
     
  11. Absane Rocket Surgeon Valued Senior Member

    Messages:
    8,989
    I think I am close to solving it myself because I reduced it to a diophantine equation... d = 2^k*[2^alpha - Z*(k-1)]. I just have to show that in the solution set of k and alpha they are the combination needed to make the 3x+1 problem work for all odd numbers. And I think it is reasonable to assume that one can say if it works for all odd numbers, then it works for all integers in Z+ (since you can divide an even number the appropriate number of times to make it odd).
     
  12. Pete It's not rocket surgery Registered Senior Member

    Messages:
    10,167
    It's easy to prove that there are no other repeating cycles that contain only one odd number.
    Is it possible to prove that there are no repeating cycles containing n odd numbers, for any or all n>1?
     
    Last edited: Sep 29, 2005
  13. funkstar ratsknuf Valued Senior Member

    Messages:
    1,390
    Ah. I lost a few days of exam reading due to examining that function. In computer science it's a well known termination problem, and termination analysis has so far been quite unable to find a good decreasing measure. I toyed with some ideas about the number of different prime factors, but it's quite difficult to get a grasp on the sucker.
     
  14. Absane Rocket Surgeon Valued Senior Member

    Messages:
    8,989
    Does anyone know if it was shown that the number of cycles for any positive odd number is unique? That is, start with 1... the number of cycles for 1+2n for n is a positive integer, no two will have the same number of iterations to terminate at 1? I believe I just shown it to be true.
     
  15. GMontag Registered Senior Member

    Messages:
    85
    You made a mistake then. There are infinitely many sets of odd numbers that take the same number of steps to hit 1. For example, 3 and 21, 227 and 1365, 14563 and 87381 (can you see the pattern?).
     
  16. funkstar ratsknuf Valued Senior Member

    Messages:
    1,390
    3,10,5,16,8,4,2,1

    21,64,32,16,8,4,2,1

    Damn you people, I'll sleep uneasy tonight, thinking about this problem again!
     
  17. Absane Rocket Surgeon Valued Senior Member

    Messages:
    8,989
    In relation to this problem... are there integers k and m such that 3^(k)*5=2^(m)-1?
     
  18. Pete It's not rocket surgery Registered Senior Member

    Messages:
    10,167
    k=1
    m=4

    No idea if there's any others.
     
  19. DaleSpam TANSTAAFL Registered Senior Member

    Messages:
    1,723
    I like funkstar's prime factor approach. The "even" operator continually gets rid of any factors of two. The sequence terminates when the "odd" operator gets rid of all other factors.

    -Dale
     
  20. Absane Rocket Surgeon Valued Senior Member

    Messages:
    8,989
    I wonder if there is a way to show it's the only solution. This is a specific case of 3^(k)*(3x+2)=2^(m)-1

    Find all integer solutions.
     
  21. Absane Rocket Surgeon Valued Senior Member

    Messages:
    8,989
    Cancel that.. stupid idea. k is always 1.
     

Share This Page