Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By chiro

Thread: Help with Collatz Conjecture

  1. #1
    Newbie
    Joined
    Aug 2016
    From
    Long Island NY
    Posts
    2

    Help with Collatz Conjecture

    I need help in seeing if I can turn an idea into a proof, or if I am merely ruining Math with my attempt at solving this. I recently watched a youtube video on the Collatz Conjecture. The Conjecture is simple enough:
    Start with a positive number n and repeatedly apply these simple rules:

    1. If n = 1, stop.
    2. If n is even, divide n by 2.
    3. If n is odd, multiply n by 3 and add 1.



    Now the way I approached the matter was first by switching n into binary format. So lets say we start out with 59 I turn it into 111011. So following the rules you would multiply by 3 or 11.

    00111011
    x 11
    _____________
    00111011
    +01110110
    _____________
    10110001
    or 177

    Then you add 1 and get 10110010 or 178.
    Next since it is even you would divide by 2 and get 89 or 1011001.

    Long story short, repeating this you end up with 1.

    So here comes the part where I need help getting this to the proof stage. But the basic concept is this, no matter what number n you start out with it can always be represented in binary, and no matter how large the first number of the string will be a 1, and if it is odd it ends with a 1, even it is a 0. The division by 2 in binary of an even number is simply truncation of the string. So you end up with the first 1 and the last 1. This causes the string to be multiplied by 3. This multiplication causes the shifting of the string to the left and keeps a 1 at its right end, thus the addition of 1 comes in and frees up the string to be truncated by the division by 2. Ultimately the end result of the odd rule and 3n will yield a string that is nothing but 1s and thus the addition of 1 will give a string with 1 and the rest 0, which is then truncated down to just 1.

    To further show that this holds true, you can change the Odd rule to 3n +/- m where m is any odd number less than 3n. The end result of this change of rules will still yield 1, as the first part of the string is 1 and the last will be 0 due to adding an odd number.

    Sorry that this is a bit rambling. Like I said, I kinda need help getting this into a way that is much easier to understand. It all makes sense to me, but maybe I'm not seeing a flaw in this understanding.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    6,566
    Thanks
    1708

    Re: Help with Collatz Conjecture

    Hey Angreifen.

    For the proof stage I'd recommend thinking about it in terms of the number of bits and showing that it will always reduce in the number given so many steps and that the last step is always 1.

    For the last step you will have to consider two cases - n is even and 2 meaning that you divide by two and get 1 and n is odd meaning you multiply n by 3 and then add 1 (which won't lead to a 1).

    If you can show that the number of bits will tend to reduce and that you can end up with a two (from certain cases where the number of bits is in that range) then you have proven the algorithm.

    Note that when you divide by two you take a bit away and when you multiply by 3 you always add a bit (and sometimes add two of them).
    Thanks from Angreifen
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2016
    From
    Long Island NY
    Posts
    2

    Re: Help with Collatz Conjecture

    chiro, thank you for the hint, sorry it took so long to reply.

    I've been thinking about figuring out how many steps it would take to get to 1. So far I know what he absolute minimum is for any number n, and that would be m or the number of bits minus 1, and that would be evident when n = 2^m where m = number of bits -1.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    6,566
    Thanks
    1708

    Re: Help with Collatz Conjecture

    I think you should try and find the number of steps it takes to reduce one bit and then go from there on in.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: May 10th 2013, 11:31 PM
  2. Replies: 0
    Last Post: Oct 17th 2010, 04:52 PM
  3. Interesting variations on the Collatz Conjecture
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 19th 2010, 09:08 AM
  4. ABC conjecture
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: May 17th 2010, 11:00 PM
  5. Collatz Conjecture
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Aug 31st 2008, 10:38 PM

Search Tags


/mathhelpforum @mathhelpforum